Approximation schemes for Euclidean k-medians and related problems

In the k-median problem we are given a set S of n points in a metric space and a positive integer k. We desire to locate k medians in space, such that the sum of the distances from each of the points of S to the nearest median is minimized. This paper gives an approximation scheme for the plane that for any c>0 produces a solution of cost at most 1+1/c times the optimum and runs in time O(n^O(c+1)). The approximation scheme also generalizes to some problems related to k-median. Our methodology is to extend Arora's techniques for the TSP, which hitherto seemed inapplicable to problems such as the k-median problem.