Computer Science Department
School of Computer Science, Carnegie Mellon University
The Integrality Gap of Capacitated Facility Location
Zoë Abrams*, Adam Meyerson, Kamesh Munagala*, Serge Plotkin*
Keywords: Algorithms, linear program rounding, approximation,
We consider the facility location problem with hard non-uniform
capacities. We examine the natural integer programming formulation
of this problem. We show that for every constant factor blowup in
capacities, the integrality gap of the LP relaxation is a constant.
We present a smooth trade-off for the cost versus the blowup in
capacities. Non-uniform capacities make the problem significantly
more difficult than the case involving uniform capacities, leading
us to develop new rounding techniques.
* Department of Computer Science, Stanford University.