### 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(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.

Original language | English (US) |
---|---|

Pages (from-to) | 106-113 |

Number of pages | 8 |

Journal | Conference Proceedings of the Annual ACM Symposium on Theory of Computing |

DOIs | |

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

- 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

Arora, S., Raghavant, P., & Rao, S. (1998). Approximation schemes for Euclidean k-medians and related problems.

*Conference Proceedings of the Annual ACM Symposium on Theory of Computing*, 106-113. https://doi.org/10.1145/276698.276718