Strong Approximation Algorithms for the Steiner Tree Problem and Related Problems

点击翻译按钮获取中文摘要

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.