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:

• A. Czumaj and C. Sohler. Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time. SIAM Journal on Computing, 39(3): 904 - 922, August 2009 (also STOC'2004).
• H. Räcke. Optimal Hierarchical Decompositions for Congestion Minimization in Networks. Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC'08), pages 255 - 264, 2008. Co-Winner of the STOC'2008 Best Paper Award.
• S. Chawla, A. Gupta, and H. Räcke. Embeddings of Negative-type Metrics and an Improved Approximation to Sparsest Cut. ACM Transactions on Algorithms, 4(2), May 2008.
• A. Czumaj and A. Lingas. Approximation Schemes for Minimum-cost k-Connectivity Problems in Geometric Graphs. Chapter 51 in Handbook of Approximation Algorithms and Metaheuristics, edited by T.F. Gonzalez, CRC Press, Boca Raton, FL, 2007.
• A. Czumaj and C. Sohler. Sublinear-Time Approximation Algorithms for Clustering via Random Sampling. Random Structures and Algorithms, 30(1-2): 226 - 256, December 2006.
• M.T. Hajiaghayi and H. Räcke. An O(n^1/2)-Approximation Algorithm for Directed Sparsest Cut. Information Processing Letters, 97(4): 156 - 160, February 2006.
• K. Dhamdhere, A. Gupta, and H. Räcke. Improved Embeddings of Graph Metrics into Random Trees. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'06), pages 61 - 69, 2006.
• A. Berger, A. Czumaj, M. Grigni, and H. Zhao. Approximation Schemes for Minimum 2-Connected Spanning Subgraphs in Weighted Planar Graphs. In Proceedings of the 13th Annual European Symposium on Algorithms (ESA'05), pages 472 - 483, 2005.
• M. Badoiu, K. Dhamdhere, A. Gupta, Y. Rabinovich, H. Räcke, R. Ravi, and A. Sidiropoulos. Approximation Algorithms for Low-distortion Embeddings into Low-dimensional Spaces. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'05), pages 119 - 128, 2005.
• A. Czumaj, M. Grigni, P. Sissokho, and H. Zhao. Approximation Schemes for Minimum 2-edge-connected and Biconnected Subgraphs in Planar Graphs. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'04), pages 489 - 498, 2004.
• H. Räcke. Minimizing Congestion in General Networks. Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02), pages 43 - 52, 2002. Winner of the FOCS'2002 Best Paper Award.
• A. Czumaj and C. Scheideler. An Algorithmic Approach to the General Lovász Local Lemma with Applications to Scheduling and Satisfiability Problems. In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC'00), pages 38 - 47, 2000.
• A. Czumaj and A. Lingas. On Approximability of the Minimum-Cost k-Connected Spanning Subgraph Problem. In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'99), pages 281 - 290, 1999.