Approximation schemes for Euclidean k-medians and related problems

Sanjeev Arora, Prabhakar Raghavant, Satish Rao

Research output: Contribution to journalConference article

213 Scopus citations

Abstract

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 languageEnglish (US)
Pages (from-to)106-113
Number of pages8
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs
StatePublished - 1998
EventProceedings of the 1998 30th Annual ACM Symposium on Theory of Computing - Dallas, TX, USA
Duration: May 23 1998May 26 1998

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint Dive into the research topics of 'Approximation schemes for Euclidean k-medians and related problems'. Together they form a unique fingerprint.

  • Cite this