Lagrangian Relaxation for the k-Median Problem: New Insights and Continuity Properties

Aaron Archer, Ranjithkumar Rajagopalan, David B. Shmoys

Abstract

This work gives new insight into two well-known approximation algorithms for the uncapacitated facility location problem: the primal-dual algorithm of Jain & Vazirani, and an algorithm of Mettu & Plaxton. Our main result answers positively a question posed by Jain & Vazirani of whether their algorithm can be modified to attain a desired “continuity” property. This yields an upper bound of 3 on the integrality gap of the natural LP relaxation of the k-median problem, but our approach does not yield a polynomial time algorithm with this guarantee. We also give a new simple proof of the performance guarantee of the Mettu-Plaxton algorithm using LP duality, which suggests a minor modification of the algorithm that makes it Lagrangian-multiplier preserving.
BibTeX
@inproceedings{archer2003lagrangian,
  author = {Aaron Archer and Ranjithkumar Rajagopalan and David B. Shmoys},
  title = {{Lagrangian Relaxation for the k-Median Problem: New Insights and Continuity Properties}},
  booktitle = {ESA},
  year = {2003},
  doi = {10.1007/978-3-540-39658-1\_6},
}

Loading related content...

Figure