The reverse greedy algorithm for the metric k-median problem |
| |
| Authors: | Marek Chrobak Claire Kenyon |
| |
| Affiliation: | a Department of Computer Science, University of California, Riverside, CA 92521, USA
b Computer Science Department, Brown University, Providence, RI 02912, USA |
| |
| 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). |
| |
| Keywords: | Analysis of algorithms Approximation algorithms Online algorithms Facility location Combinatorial optimization |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
