Improved Steiner Tree Approximation in GraphsReport
The Steiner tree problem in weighted graphs seeks a minimum weight connected subgraph containing a given subset of the vertices (terminals). We present a new polynomial-time heuristic with an approximation ratio approaching 1 + 1~___33 ~ 1.55, which improves upon the previously best-known approximation algorithm of  with performance ratio ~ 1.59. In quasi-bipartite graphs (i.e., in graphs where all non-terminals are pairwise disjoint), our algorithm achieves an approximation ratio of ~ 1.28, whereas the previously best method achieves an approximation ratio approachiug 1.5 . 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 . 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  achieves an approximation ratio of 1.5 in quasi-blpartite graphs, thus providing the first known non-trivial performance ratio of this well-known method.
Note: Abstract extracted from PDF text
All rights reserved (no additional license for public reuse)
Robins, Gabriel, and Alexander Zelikovsky. "Improved Steiner Tree Approximation in Graphs." University of Virginia Dept. of Computer Science Tech Report (1999).
University of Virginia, Department of Computer Science