Institut für Informatik
Abteilung V

Universität Bonn -> Institut für Informatik -> Abteilung V
CS-APX-Reports 2008 Copyright 2008 Universität Bonn, Institut für Informatik, Abt. V


On the Approximability of Dense Steiner Problems
Mathias Hauptmann
[Download PostScript] [Download PDF]

The ε-Dense Steiner Tree Problem was defined by Karpinski and Zelikovsky (1997) who proved that for each ε>0, this problem admits a PTAS. Based on their method we consider here dense versions of various Steiner Tree problems. In particular, we give polynomial time approximation schemes for the ε-Dense k-Steiner Tree Problem, the ε-Dense Prize Collecting Steiner Tree Problem, the ε-Dense k-Steiner Tree Problem and the ε-Dense Group Steiner Tree Problem. For the dense version of the Steiner Forest Problem we obtain an approximation algorithm that performs well if the number of terminal sets is small compared to the total number of terminals.

Last Change: 11/05/14 at 10:42:03
Universität Bonn -> Institut für Informatik -> Abteilung V