A multiexchange local search algorithm for the capacitated facility location problem

A multiexchange local search algorithm for the capacitated facility location problem

0.00 Avg rating0 Votes
Article ID: iaor20061134
Country: United States
Volume: 30
Issue: 2
Start Page Number: 389
End Page Number: 403
Publication Date: May 2005
Journal: Mathematics of Operations Research
Authors: , ,
Keywords: graphs, heuristics
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)−e and 3+2√(2)+e for any given constant e>0. The previously known best approximation ratio for the CFLP is 7.88, as shown by Mahdian and Pál, based on the operations proposed by Pál et al. Our upper bound 3+2√(2)+e also matches the best-known ratio, obtained by Chudak and Williamson, 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.

Reviews

Required fields are marked *. Your email address will not be published.