A polynomial-time approximation scheme for Euclidean Steiner forest
October 5, 2008
Glencora Borradaile, Philip Klein and Claire Mathieu
We give a randomized O(n2 log n)-time approximation scheme for the Steiner forest problem in the Euclidean plane. For every fixed ε > 0 and given any n pairs of terminals in the plane, our scheme finds a (1 + ε)- approximation to the minimum-length forest that connects every pair of terminals.
Symposium of Foundations of Computer Science (FOCS), Philadelphia, Pennsylvania, 2008.
