Skip to main content Skip to navigation

Approximation Algorithms

Numerous practical optimisation problems are NP-hard and therefore do not have polynomial-time algorithms unless the polynomial hierarchy collapses. In practise these problems are commonly addressed with heuristics that quickly provide a solution, but do not give information on the solution' quality. An approximation algorithm instead is an algorithm that not only runs quickly, i.e., in polynomial time, but also gives a guarantee on how far the obtained solution may be away from optimal.

The study of approximation algorithms has become a standard way of dealing with NP-hard problems in the theory community, but it is also becoming more and more accepted in practise as theoretical analysis provides a deeper understanding of the problem at hand. One typical task in the design process of an approximation algorithm is to find worst-case inputs for a proposed algorithm. This, of course, is also invaluable for the evaluation of heuristics as one needs to be aware on which instances a heuristic performs well. In this way the design and theoretical analysis of approximation algorithms is also an important tool for evaluating heuristics in practical applications.

In DIMAP the design of approximation algorithms covers many different areas, from string algorithms and routing problems to graph partitioning and network optimization. Especially in the latter problem area the algorithms are also compared to heuristics derived by integer programming techniques.

Sample publications: