Item Details

Better Approximation Bounds for the Network and Euclidean Steiner Tree Problems

Zelikovsky, Alexander
Format
Report
Author
Zelikovsky, Alexander
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.
Language
English
Date Received
20121029
Published
University of Virginia, Department of Computer Science, 1996
Published Date
1996
Collection
Libra Open Repository
Logo for In CopyrightIn Copyright

Availability

Access Online