A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest
Authors:
- Glencora BorradaileGBGlencora Borradaile
- Philip N. KleinPKPhilip N. Klein
- Claire MathieuCMClaire Mathieu
- 1 October 2008
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 115-124
Abstract
We give a randomized O(n2 log n)-time approximation scheme for the Steiner forest problem in the Euclidean plane. For every fixed epsi > 0 and given any n pairs of terminals in the plane, our scheme finds a (1 + epsi)- approximation to the minimum-length forest that connects every pair of terminals.Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- 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
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problemsJournal of the ACM, 1998
- Approximation schemes for Euclidean k-medians and related problems1998
- Approximating geometrical graphs via “spanners” and “banyans”1998
- When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on NetworksSIAM Journal on Computing, 1995
- The Steiner problem with edge lengths 1 and 2Information Processing Letters, 1989