CMU-CS-02-199
Computer Science Department
School of Computer Science, Carnegie Mellon University


CMU-CS-02-199

The Integrality Gap of Capacitated Facility Location

Zoë Abrams*, Adam Meyerson, Kamesh Munagala*, Serge Plotkin*

December 2002

CMU-CS-02-199.ps
CMU-CS-02-199.pdf


Keywords: Algorithms, linear program rounding, approximation, facility location


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.

9 pages

* Department of Computer Science, Stanford University.

9 pages

* Department of Computer Science, Stanford University.

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by [email protected]