Better approximation bounds for the network and Euclidean Steiner tree problems

The network and Euclidean Steiner tree problems require a shortest tree spanning a given vertex subset within a network G=(V,E,d) and Euclidean plane, respectively. For these problems, we present a series of heuristics finding approximate Steiner trees with performance guarantees coming arbitrary close to 1+ln 2= 1.693... and 1+ln(2/sqrt3) = 1.1438..., respectively. The best previously known corresponding values are close to 1.746 and 1.1546.

Zelikovsky, Alexander. "Better approximation bounds for the network and Euclidean Steiner tree problems." University of Virginia Dept. of Computer Science Tech Report (1996).