29.10.2007

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.