This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Zhang, J. Articles by Ye, Y. Search for Related Content

A Multiexchange Local Search Algorithm for the Capacitated Facility Location Problem

IOMS-Operations Management, Stern School of Business, New York University, 44 W. 4th Street, Suite 8-66, New York, New York 10012-1126
Warwick Business School, The University of Warwick, Coventry, England, UK
Department of Management Science and Engineering, Stanford University, Stanford, California 94305
jzhang{at}stern.nyu.edu
b.chen{at}warwick.ac.uk
yinyu-ye{at}stanford.edu

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 + 22 – and 3 + 22 + 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+22+ 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.

Key Words: capacitated facility location; approximation algorithm; local search algorithm
History: Received: October 20, 2003; revision received: March 5, 2004;