Item Details

Print View

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
2012-10-29
Published
University of Virginia, Department of Computer Science, 1996
Published Date
1996
Collection
Libra Open Repository
In CopyrightIn Copyright
▾See more
▴See less

Availability

Access Online