neal young / Chrobak06Reverse

Information Processing Letters 97:6872(2006); COCOON'05The 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)$.Journal version of [2005].
© Copyrights are reserved by the publishers.
Download for personal and limited academic use only.