Computer Science – Data Structures and Algorithms
Scientific paper
2002-05-18
ACM-SIAM Symposium on Discrete Algorithms (2000)
Computer Science
Data Structures and Algorithms
Scientific paper
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.
No associations
LandOfFree
K-Medians, Facility Location, and the Chernoff-Wald Bound does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with K-Medians, Facility Location, and the Chernoff-Wald Bound, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and K-Medians, Facility Location, and the Chernoff-Wald Bound will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-599187