A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest

Authors:
  • GBGlencora Borradaile
    Glencora Borradaile
  • PKPhilip N. Klein
    Philip N. Klein
  • CMClaire Mathieu
    Claire Mathieu

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.