Facility location with nonuniform hard capacities
- 1 January 2001
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15525244,p. 329-338
- https://doi.org/10.1109/sfcs.2001.959907
Abstract
The authors give the first constant factor approximation algorithm for the facility location problem with nonuniform, hard capacities. Facility location problems have received a great deal of attention in recent years. Approximation algorithms have been developed for many variants. Most of these algorithms are based on linear programming, but the LP techniques developed thus far have been unsuccessful in dealing with hard capacities. A local-search based approximation algorithm (M. Korupolu et al., 1998; F.A. Chudak and D.P. Williamson, 1999) is known for the special case of hard but uniform capacities. We present a local-search heuristic that yields an approximation guarantee of 9 + /spl epsi/ for the case of nonuniform hard capacities. To obtain this result, we introduce new operations that are natural in this context. Our proof is based on network flow techniques.Keywords
This publication has 8 references indexed in Scilit:
- Improved combinatorial algorithms for the facility location and k-median problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Primal-dual approximation algorithms for metric facility location and k-median problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Local search heuristic for k-median and facility location problemsPublished by Association for Computing Machinery (ACM) ,2001
- Improved Approximation Algorithms for Capacitated Facility Location ProblemsPublished by Springer Nature ,1999
- Plant location with minimum inventoryMathematical Programming, 1998
- An approximation algorithm for the generalized assignment problemMathematical Programming, 1993
- Approximation algorithms for scheduling unrelated parallel machinesMathematical Programming, 1990
- A Heuristic Program for Locating WarehousesManagement Science, 1963