Strong Approximation Algorithms for the Steiner Tree Problem and Related Problems

• Applicant: Professor Dr. Markus Chimani
• Subject Area: Theoretical Computer Science
• Term: from 2016 to 2022
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 317997620

We consider classical and practically relevant NP-hard problems in the area of topological network design. The probably best known such problem---besides the polynomial-time solvable spanning tree problem---is the Steiner tree problem: given a weighted graph, find a minimum-weight tree connecting a given set of terminal nodes. In practice, this and related problems arise in as diverse fields as, e.g., telecommunication networks, VLSI design, and geography.In previous studies, the theoretically strong approximation algorithms for the Steiner tree problem proved to be rather impractical due to their central concepts. The goal of this project is on the one hand to make these concepts more applicable in practice. On the other hand, we aim to develop new related but more directly applicable concepts that lead to similar quality guarantees.Apart from the classical Steiner tree problem, we also consider the problems of 2-connected network design, spanners, and directed Steiner trees, as well as practically relevant problems from geography/geoinformatic applications.

• DFG Programme: Research Grants