An Approximation Algorithm for the Steiner Tree Problem

Abstract: "For a set S contained in a metric space, a Steiner tree of S is a spanning tree of a superset of S. Finding a minimum cost Steiner tree is an NP-hard problem. We give an approximation algorithm which in several cases yields provably better performance guarantee compared to exisiting algorithms. In particular, the cost of our solutions in the case of weighted graphs does not exceed 16/9 times the optimum, while in the case of rectilinear metric on the plane it is within 1.35 times the optimum, improving upon previously proved performance ratios of 11/6 and 1.5, respectively."