A polynomial-time approximation scheme for Euclidean Steiner forest
Preprint
Abstract
We give a randomized O(n polylog n)-time approximation scheme for the Steiner forest problem in the Euclidean plane. For every fixed eps > 0 and given n terminals in the plane with connection requests between some pairs of terminals, our scheme finds a (1 + eps)-approximation to the minimum-length forest that connects every requested pair of terminals.Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- An O ( n log n ) approximation scheme for Steiner tree in planar graphsACM Transactions on Algorithms, 2009
- A Nearly Linear-Time Approximation Scheme for the Euclidean k-Median ProblemSIAM Journal on Computing, 2007
- Approximation schemes for NP-hard geometric optimization problems: a surveyMathematical Programming, 2003
- When Hamming Meets Euclid: The Approximability of Geometric TSP and Steiner TreeSIAM Journal on Computing, 2000
- Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related ProblemsSIAM Journal on Computing, 1999
- When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on NetworksSIAM Journal on Computing, 1995
- Use of dynamic trees in a network simplex algorithm for the maximum flow problemMathematical Programming, 1991
- The Steiner problem with edge lengths 1 and 2Information Processing Letters, 1989
- On the Computational Complexity of Combinatorial ProblemsNetworks, 1975
- An efficient algorith for determining the convex hull of a finite planar setInformation Processing Letters, 1972