neal young / Young00Kmedians
-
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 [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 (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.