Primal-Dual Approximation Algorithms for Metric Facility Location and k-Median Problems

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 graph. The main algorithmic idea is a new extension of the primal-dual schema to handle a primal-dual pair of LP's that are not a covering-packing pair. 1 Introduction Given costs for opening facilities and costs for connecting cities to facilities, the uncapacitated facility location problem seeks a minimum cost solution that connects each city to an open facility. Clearly, this problem is applicable to a number of industrial situations. For this reason it has occupied a central place in operations research since the early 60's [3, 23, 31, 32], and has been studied from the perspectives of worst case analysis, probabilistic..