Approximation schemes for the 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 solu-tion of cost at most 1+ 1/c times the optimum and runs in time O(nO(c+1)). The approxima-tion scheme also generalizes to some problems related to k-median. Our methodology is to extend Arora’s [1, 2] techniques for the TSP, which hitherto seemed inapplicable to problems such as the k-median problem.