A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest

摘要

We give a randomized O(n polylog n)-time approximation scheme for the Steiner forest problem in the Euclidean plane. For every fixed epsilon > 0 and given n terminals in the plane with connection requests between some pairs of terminals, our scheme finds a (1 + epsilon) approximation to the minimum-length forest that connects every requested pair of terminals.