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 l ocation problem and the metric k-median problem achieving guarantees of 3 a nd 6 respectively. The distinguishing feature of our algorithms is their lo w 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 comple te bipartite graph on cities and facilities. The main algorithmic ideas are a new extension of the primal-dual schema and the use of Lagrangian relaxa tion to derive approximation algorithms.