Key points are not available for this paper at this time.
The Steiner tree problem in weighted graphs seeks a minimum weight connected subgraph containing a given subset of vertices (terminals). We present a new polynomial-time heuristic with an approximation ratio approaching 1+ ln 3 2 1:55, which improves upon the previously best-known approximation algorithm of 9 with performance ratio 1:59. In quasi-bipartite graphs (i.e., in graphs where all nonterminals are pairwise disjoint), our algorithm achieves an approximation ratio of 1:28, whereas the previously best method achieves an approximation ratio approaching 1:5 18. For complete graphs with edge weights 1 and 2, we show that our heuristic has an approximation ratio approaching 1:28, which improves upon the previously best-known ratio of 4 3 4. Our method is considerably simpler and easier to implement than previous approaches. Our techniques can also be used to prove that the Iterated 1-Steiner heuristic 13 achieves an approximation ratio of 1:5 in quasi-bipar...
Robins et al. (Tue,) studied this question.