K-Medians, Facility Location, and the Chernoff-Wald Bound
<|reference_start|>K-Medians, Facility Location, and the Chernoff-Wald Bound: 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/epsilon)k medians and having cost at most (1+epsilon) times the cost of the best solution that uses at most k medians. Here epsilon > 0 is an input to the algorithm. In comparison, the best previous algorithm (Jyh-Han Lin and Jeff Vitter, 1992) had a (1+1/epsilon)ln(n) term instead of the ln(n+n/epsilon) 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 (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.<|reference_end|>
@article{young2002k-medians,,
    title={K-Medians, Facility Location, and the Chernoff-Wald Bound},
    author={Neal E. Young},
    journal={ACM-SIAM Symposium on Discrete Algorithms (2000)},
    year={2002},
    archivePrefix={arXiv},
    eprint={cs/0205047},
    primaryClass={cs.DS cs.DM}
}