Journal
INFORMATION PROCESSING LETTERS
Volume 97, Issue 2, Pages 68-72Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.ipl.2005.09.009
Keywords
analysis of algorithms; approximation algorithms; online algorithms; facility location; combinatorial optimization
Categories
Ask authors/readers for more resources
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 Omega(log n/log log n) and O(log n). (c) 2005 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available