A polynomial-time approximation scheme for Euclidean Steiner forest

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.

arXiv commentThis version is more recent than that appearing in the FOCS proceedings. The partition step has been corrected and the overall presentation has been clarified and formalized. This paper has been accepted to TALG