On Uniform Capacitated $k$-Median Beyond the Natural LP Relaxation
Author:
Preprint
Abstract
In this paper, we study the uniform capacitated $k$-median problem. Obtaining a constant approximation algorithm for this problem is a notorious open problem; most previous works gave constant approximations by either violating the capacity constraints or the cardinality constraint. Notably, all these algorithms are based on the natural LP-relaxation for the problem. The LP-relaxation has unbounded integrality gap, even when we are allowed to violate the capacity constraints or the cardinality constraint by a factor of $2-\epsilon$. Our result is an $\exp(O(1/\epsilon^2))$-approximation algorithm for the problem that violates the cardinality constraint by a factor of $1+\epsilon$. This is already beyond the capability of the natural LP relaxation, as it has unbounded integrality gap even if we are allowed to open $(2-\epsilon)k$ facilities. Indeed, our result is based on a novel LP for this problem. The version as we described is the hard-capacitated version of the problem, as we can only open one facility at each location. This is as opposed to the soft-capacitated version, in which we are allowed to open more than one facilities at each location. We give a simple proof that in the uniform capacitated case, the soft-capacitated version and the hard-capacitated version are actually equivalent, up to a small constant loss in the approximation ratio.
Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- Approximation algorithms for hard capacitated k-facility location problemsEuropean Journal of Operational Research, 2015
- Approximation Algorithms for Metric Facility Location ProblemsSIAM Journal on Computing, 2006
- A Multiexchange Local Search Algorithm for the Capacitated Facility Location ProblemMathematics of Operations Research, 2005
- Improved approximation algorithms for capacitated facility location problemsMathematical Programming, 2004
- Greedy facility location algorithms analyzed using dual fitting with factor-revealing LPJournal of the ACM, 2003
- Improved Approximation Algorithms for the Uncapacitated Facility Location ProblemSIAM Journal on Computing, 2003
- Approximation algorithms for geometric median problemsInformation Processing Letters, 1992