The reverse greedy algorithm for the metric k-median problem
- Author(s): Chrobak, M;
- Kenyon, C;
- Young, N
- et al.
Published Web Locationhttps://arxiv.org/pdf/cs/0504104
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.