Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 2007 Copyright 2007 University of Bonn, Department of Computer Science, Abt. V
85283

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
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V