K-Medians, Facil i ty Location, and the Chernoff-Wald Bound
Neal E. Young · 2000
We study the general (non-metric) facility-location and weighted k-medians problems, as well as the fractional facility-location and k-medians problems. We describe a natural randomized rounding scheme and use it to derive approximation algorithms for all of these problems. For facility location and weighted k-medians, the re-spective algorithms are polynomial-time [HAk + d]- and [(1 + e)d; In(n + n/e)k]-approximation algorithms. These performance guarantees improve on the best previous per-formance guarantees, due respectively to Hochbaum (1982) and Lin and Vitter (1992). For fractional k-medians, the al-gorithm is a new, Lagrangian-relaxation, [(1 + e)d, (1 + e)k]-approximation algorithm. It runs in O(kln(n/e)/e 2) linear-time iterations. For fractional facilities-location (a generalization of frac-tional weighted set cover), the algorithm is a Lagrangian-relaxation, ~(1 + e)k]-approximation algorithm. It runs in O(nln(n)/e ~) linear-time iterations and is essentially the same as an unpublished Lagrangian-relaxation algorithm due to Garg (1998). By recasting his analysis probabilis-tically and abstracting it, we obtain an interesting (and as far as we know new) probabilistic bound that may be of independent interest. We call it the Chernoff- Wald bound.