A Multiexchange Local Search Algorithm for the Capacitated Facility Location Problem
Authors:
- 1 May 2005
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 30 (2) , 389-403
Abstract
We present a multiexchange local search algorithm for approximating the capacitated facility location problem (CFLP), where a new local improvement operation is introduced that possibly exchanges multiple facilities simultaneously. We give a tight analysis for our algorithm and show that the performance guarantee of the algorithm is between 3 + 2√2 − ε and 3 + 2√2 + ε for any given constant ε > 0. The previously known best approximation ratio for the CFLP is 7.88, as shown by Mahdian and Pál (2003. Universal facility location. Proc. 11th Annual Eur. Sympos. Algorithms (ESA), 409–421), based on the operations proposed by Pál et al. (2001. Facility location with hard capacities. Proc. 42nd IEEE Sympos. Foundations Comput. Sci. (FOCS), 329–338). Our upper bound 3+2√2+ε also matches the best-known ratio, obtained by Chudak and Williamson (1999. Improved approximation algorithm for capacitated facility location problems. Proc. 7th Conf. Integer Programming Combin. Optim. (IPCO), 99–113), for the CFLP with uniform capacities. In order to obtain the tight bound of our new algorithm, we make interesting use of the notion of exchange graph of Pál et al. and techniques from the area of parallel machine scheduling.Keywords
This publication has 15 references indexed in Scilit:
- Improved Combinatorial Approximation Algorithms for the k-Level Facility Location ProblemSIAM Journal on Discrete Mathematics, 2004
- Universal Facility Location2003
- Improved Approximation Algorithms for the Uncapacitated Facility Location ProblemSIAM Journal on Computing, 2003
- Improved Approximation Algorithms for Metric Facility Location Problems2002
- Local search heuristic for k-median and facility location problems2001
- The Capacitated K-Center ProblemSIAM Journal on Discrete Mathematics, 2000
- A 3-approximation algorithm for the -level uncapacitated facility location problemInformation Processing Letters, 1999
- Improved Approximation Algorithms for Capacitated Facility Location Problems1999
- Greedy Strikes Back: Improved Facility Location AlgorithmsJournal of Algorithms, 1999
- A Heuristic Program for Locating WarehousesManagement Science, 1963