Local Search Heuristics for Budget Constrained K-Median Problem.

$k$-median, and $k$-center are well studied problems in operations research. In this paper, we present local search algorithm to obtain good solutions with respect to these measures. It is easy to show that both $k$-median, and $k$-center cannot be approximated within constants simultaneously. So we consider one of natural relaxations of the problem, namely minimizing the cost of $k$-median solution when a bound is placed on the $k$-center measure it induces. We call this problem as {\em budgeted $k$-median problem}. Our local search technique produces a constant factor approximation of the median cost, while ensuring that the bound on the $k$-center measure is not violated by more than a constant factor. Our technique is based on local search technique presented in ~\cite{aryaSTOC01}. The key idea of our technique is the preprocessing of the input to satisfy the {\em min-max} criteria of the optimization problem. The best approximation we obtain provides a factor 5 approximation to the median cost.

By: Vinayaka Pandit, Naveen Garg, Rohit Khandekar.

Published in: RI03002 in 2003


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to reports@us.ibm.com .