Network theory deals with the study of graphs as a description of relations between discrete objects. This very abstract and general notion includes for example the study of the World Wide Web, the Internet, social networks, networks in tele-communcications, or logistic networks in supply chain management.

Within this vast area, the research within DIMAP mainly focuses on Network optimisation which deals with solving certain problems on networks, like e.g. the Traveling Salesperson problem, facility location, shortest path problems, cut problems, or flow problems. Another aspect are network design problems where the output of the problem is a network.

We approach problems of this type from a theoretical perspective by designing approximation algorithms for them, i.e., algorithms that guarantee, both, polynomial running time and a certain solution quality, but also from a heuristic perspective where we aim at finding the optimum solution with the caveat that we cannot guarantee a polynomial running time anymore. See also Combinatorial Optimisation .

Sample publications:

• H. Räcke. Optimal Hierarchical Decompositions for Congestion Minimization in Networks. In 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.
• A. Admaszek, A. Czumaj, and A. Lingas. PTAS for k-tour Cover Problem on the Plane for Moderately Large Values of k. In Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC'09), pages 994 - 1003, 2009.
• 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.
• M.T. Hajiaghayi, R.D. Kleinberg, F.T. Leighton, and H. Räcke. Oblivious Routing on Node-Capacitated and Directed Graphs. ACM Transactions on Algorithms, 3(4), November 2007.
• 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.
• K. Andreev and H. Räcke. Balanced Graph Partitions. Theory of Computing Systems, 39(6): 929 - 939, November 2006.
• A. Czumaj and W. Rytter. Broadcasting Algorithms in Radio Networks with Unknown Topology. Journal of Algorithms, 60(2): 115 - 143, August 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.
• Y. Azar, E. Cohen, A. Fiat, H. Kaplan, and H. Räcke. Optimal Oblivious Routing in Polynomial Time. Journal of Computer and System Sciences, 69(3): 383 - 394, November 2004.
• H. Räcke. Minimizing Congestion in General Networks. In Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02), pages 43 - 52, 2002. Co-Winner of the FOCS'2002 Best Paper Award.