A Polynomial Time Approximation Scheme for Euclidean Minimum Cost k-Connectivity

摘要

We present polynomial-time approximation schemes for the problem of finding a minimum-cost k-connected Euclidean graph on a finite point set in R~d. The cost of an edge in such a graph is equal to the Euclidean distance between its endpoints. Our schemes use Steiner points. For every given c > 1 and a set S of n points in R~d, a randomized version of our scheme finds an Euclidean graph on a superset of 5 which is k-vertex (or k-edge) connected with respect to S, and whose cost is with probability 1/2 within (1 +1/c ) of the minimum cost of a k-vertex (or k-edge) connected Euclidean graph on 5, in time n · (logn)(O(c(dk)~1/2)~(d-1) · 2((O(c(dk)~(1/2))~(d-1)~1. We can derandomize the scheme by increasing the running time by a factor O(n). We also observe that the time cost of the derandomization of the PTA schemes for Euclidean optimization problems in K~d derived by Arora can be decreased by a multiplicative factor of Ω(n~(d-1)).