Tighter bounds for graph Steiner tree approximation

The classical 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 that achieves a best-known approximation ratio of 1 + ln 3/2 approximate to 1.55 for general graphs and best-known approximation ratios of approximate to 1.28 for both quasi-bipartite graphs (i.e., where no two nonterminals are adjacent) and complete graphs with edge weights 1 and 2. Our method is considerably simpler and easier to implement than previous approaches. We also prove the first known nontrivial performance bound (1.5 center dot OPT) for the iterated 1-Steiner heuristic of Kahng and Robins in quasi-bipartite graphs.