IMPROVED APPROXIMATIONS FOR THE STEINER TREE PROBLEM

For a set S contained in a metric space, a Steiner tree of S is a tree that connects the points in S. Finding a minimum cost Steiner tree is an NP-hard problem in Euclidean and rectilinear metrics, as well as in graphs. We give an approximation algorithm and show that the worst-case ratio of the cost of our solutions to the optimal cost is better than previously known ratios in graphs and in the rectilinear metric on the plane. Our method offers a trade-off between the running time and the ratio: on one hand it always allows improvement of the ratio, on the other hand it allows previously known ratios to be obtained with greater efficiency. We use properties of optimal rectilinear Steiner trees to obtain significantly better ratio and running time in the rectilinear metric. (C) 1994 Academic Press, Inc.