Skip to main content
eScholarship
Open Access Publications from the University of California

UC Riverside

UC Riverside Previously Published Works bannerUC Riverside

The reverse greedy algorithm for the metric k-median problem

  • Author(s): Chrobak, M
  • Kenyon, C
  • Young, N
  • et al.

Published Web Location

https://arxiv.org/pdf/cs/0504104
No data is associated with this publication.
Abstract

The Reverse Greedy algorithm (RGreedy) for the k-median problem works as follows. It starts by placing facilities on all nodes. At each step, it removes a facility to minimize the total distance to the remaining facilities. It stops when k facilities remain. We prove that, if the distance function is metric, then the approximation ratio of RGreedy is between Ω(logn/loglogn) and O(logn). © 2005 Elsevier B.V. All rights reserved.

Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.

Item not freely available? Link broken?
Report a problem accessing this item