- A Multi-Exchange Local Search Algorithm for the Capacitated Facility Location Problem Jiawei Zhang (jiazhangstanford.edu) Bo Chen (Bo.Chenwbs.ac.uk) Yinyu Ye (yinyu-yestanford.edu) Abstract: We present a multi-exchange 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\sqrt{2}-\epsilon$ and $3+2\sqrt{2}+\epsilon$ for any given constant $\epsilon>0$. Previously known best approximation ratio for the CFLP is $7.88$, due to Mahdian and P\'{a}l (2003), based on the operations proposed by P\'{a}l, Tardos and Wexler (2001). Our upper bound $3+2\sqrt{2}+\epsilon$ also matches the best known ratio, obtained by Chudak and Williamson (1999), for the CFLP with uniform capacities. In order to obtain the tight bound of our new algorithm, we make interesting use of techniques from the area of parallel machine scheduling. Keywords: capacitated facility location, approximation algorithm, local search algorithm. Category 1: Combinatorial Optimization (Approximation Algorithms ) Category 2: Network Optimization Citation: Working paper, Oct. 2003, Department of Management Science and Engineering, Stanford University, CA, 94305 Download: [Postscript][PDF]Entry Submitted: 10/20/2003Entry Accepted: 10/21/2003Entry Last Modified: 10/20/2003Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.