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(nO(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.
|Original language||English (US)|
|Number of pages||8|
|Journal||Conference Proceedings of the Annual ACM Symposium on Theory of Computing|
|State||Published - 1998|
|Event||Proceedings of the 1998 30th Annual ACM Symposium on Theory of Computing - Dallas, TX, USA|
Duration: May 23 1998 → May 26 1998
All Science Journal Classification (ASJC) codes