The reverse greedy algorithm for the metric k-median problem
<|reference_start|>The reverse greedy algorithm for the metric k-median problem: 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 resulting total distance from the customers 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 ?(log n/ log log n) and O(log n).<|reference_end|>
@article{chrobak2005the,
    title={The reverse greedy algorithm for the metric k-median problem},
    author={Marek Chrobak and Claire Kenyon and Neal E. Young},
    journal={Information Processing Letters 97:68-72(2006)},
    year={2005},
    doi={10.1016/j.ipl.2005.09.009},
    archivePrefix={arXiv},
    eprint={cs/0504104},
    primaryClass={cs.DS}
}