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.

* Department of Computer Science, Stanford University.

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

This page maintained by reports@cs.cmu.edu