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; O (m log m ) and O (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.