A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest

We give a randomized O(n 2 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.

Authors

• Glencora Borradaile
• Philip N. Klein
• Claire Mathieu

Keywords

• Polynomials
• Computer science
• Steiner trees
• Combinatorial mathematics
• Costs
• Approximation algorithms
• Portals
• Dynamic programming
• Estimation Strategy
• Polynomial Time Approximation Scheme
• 2-dimensional Space
• Terminal Pair
• Increase In Length
• Feasible Solution
• Bounding Box
• Set Of Cells
• Loop Iteration
• Partitioning Algorithm
• Number Of Terminals
• Compact Configuration
• Quadtree
• approximation algorithm
• approximation scheme
• Euclidean plane
• Steiner forest