Better approximation bounds for the network and Euclidean Steiner tree problemsReport
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.
All rights reserved (no additional license for public reuse)
Zelikovsky, Alexander. "Better approximation bounds for the network and Euclidean Steiner tree problems." University of Virginia Dept. of Computer Science Tech Report (1996).
University of Virginia, Department of Computer Science