Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation

We present approximation algorithms for the metric uncapacitated facility location problem and the metric k-median problem achieving guarantees of 3 and 6 respectively. The distinguishing feature of our algorithms is their low running time: 0(m log m) and 0(m log m(L + log(n))) respectively, where n and m are the: total number of vertices and edges in the underlying complete bipartite graph on cities and facilities. The main algorithmic ideas are a new extension of the primal-dual schema and the use of Lagrangian relaxation to derive approximation algorithms.