Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
 
Abteilung V

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

29.10.2007

Approximation Hardness of the (1,2)-Steiner Tree Problem
Mathias Hauptmann
[Download PostScript] [Download PDF]

We give a survey on the approximation hardness of the Steiner Tree Problem. While for the general metric case, Chlebik and Chlebikova [CC02] prove a lower bound of ≈ 1.01, this result does not seem to apply to bounded metrics. We show that combining an L-reduction from the Bounded Degree Vertex Cover Problem to the (1,2)-Steiner Tree Problem due to Bern and Plassmann [BP89] with approximation hardness results of Berman and Karpinski [BK03], one obtains the currently best known lower bound of ≈ 1.0026 for the approximability of the (1,2)-Steiner Tree Problem.

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

Powered by Zope