Better approximation bounds for the network and Euclidean Steiner tree problems

Report
Author:Zelikovsky, Alexander, Department of Computer ScienceUniversity of Virginia
Abstract:

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.

Rights:
All rights reserved (no additional license for public reuse)
Language:
English
Source Citation:

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

Publisher:
University of Virginia, Department of Computer Science
Published Date:
1996