neal young / Young00Kmedians

  • Png/Young00Kmedians.png The paper gives approximation algorithms for the $k$-medians and facility-location problems (both NP-hard). For $k$-medians, the algorithm returns a solution using at most $\ln(n+n/ε) k$ medians and having cost at most $(1+ε)$ times the cost of the best solution that uses at most $k$ medians. Here $ε>0$ is an input to the algorithm. In comparison, the best previous algorithm [Lin and Jeff Vitter, 1992] had a $(1+1/ε)\ln n$ term instead of the $\ln(n+n/ε)$ term in the performance guarantee. For facility location, the algorithm returns a solution of cost at most $d+\ln(n) k$, provided there exists a solution of cost $d+k$ where $d$ is the assignment cost and $k$ is the facility cost. In comparison, the best previous algorithm [Dorit Hochbaum, 1982] returned a solution of cost at most $\ln(n)(d+k)$. For both problems, the algorithms currently provide the best performance guarantee known for the general (non-metric) problems.

    The paper also introduces a new probabilistic bound (the so-called Chernoff-Wald bound) for bounding the expectation of the maximum of a collection of sums of random variables, when each sum contains a random number of terms. The bound is used to analyze the randomized rounding scheme that underlies the algorithms.

© Copyrights are reserved by the publishers.
Download for personal and limited academic use only.