On Uniform Capacitated k -Median Beyond the Natural LP Relaxation
Author:
Open Access
- 14 January 2017
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 13 (2) , 1-18
Abstract
In this article, we study the uniform capacitated k -median (CKM) problem. In the problem, we are given a set F of potential facility locations, a set C of clients, a metric d over F ∪ C , an upper bound k on the number of facilities that we can open, and an upper bound u on the number of clients that each facility can serve. We need to open a subset S ⊆ F of k facilities and connect clients in C to facilities in S so that each facility is connected by at most u clients. The goal is to minimize the total connection cost over all clients. 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 of 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 − ϵ. Our result is an exp ( O (1/ϵ 2 ))-approximation algorithm for the problem that violates the cardinality constraint by a factor of 1 + ϵ. In other words, we find a solution that opens at most (1 + ϵ) k facilities whose cost is at most exp ( O (1/ϵ 2 )) times the optimum solution when at most k facilities can be open. 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 − ϵ) k facilities. Indeed, our result is based on a novel LP for this problem. It is our hope that this LP is the first step toward a constant approximation for CKM. The version that 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 facility at each location. The hard capacitated version is more general, since one can convert a soft capacitated instance to a hard capacitated instance by making enough copies of each facility 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 23 references indexed in Scilit:
- A 5-Approximation for Capacitated Facility Location2012
- A 1.488 Approximation Algorithm for the Uncapacitated Facility Location Problem2011
- An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem2007
- 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 metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxationJournal of the ACM, 2001
- Approximation algorithms for geometric median problemsInformation Processing Letters, 1992