Many problems in combinatorial optimization can be stated in the language of graph theory. However, the resulting problems like the Steiner tree problem or graph coloring problems tend to be NP-hard and cannot be solved efficiently.
Nevertheless problems of this kind arise in many applications and must be dealt with algorithmically. The following approaches are investigated in our work group:
- Approximation algorithms.
- These are methods find an approximate solution, which is guaranteed to be close to the theoretical optimum up to a certain factor.
- Randomized algorithms.
- For many problems algorithms are known that perform certain decisions at random in order to find a good solution with (provably) high probability. Quite often, randomized algorithms are simpler or faster than deterministic ones.
- Probabilistic analysis of algorithms.
- Here the goal is to prove that an algorithm will find a good solution on almost all instances of the problem, assuming they are distributed according to a given distribution.
Complementary to these investigations we also deal with the question of inapproximability of problems, i.e., proving that a given problem is not only hard to solve exactly (under reasonble complexity theoretical assumptions), but also cannot be approximated up to a certain factor.
Deutsch