View article

In t. he 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 t. he nearest median is miniied. Thii paper gives an approximation scheme for the plane that for any c> 0 produces a solution of cost at most 1+ l/c times the optimum and runs in t. ime Q (~ z~@+~)). The apprcximation scheme also generalizes to some problems related to k-median.