2004 | OriginalPaper | Buchkapitel
A Multi-exchange Local Search Algorithm for the Capacitated Facility Location Problem
verfasst von : Jiawei Zhang, Bo Chen, Yinyu Ye
Erschienen in: Integer Programming and Combinatorial Optimization
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 ε> 0. Previously known best approximation ratio for the CFLP is 7.88, due to Mahdian and Pál (2003), based on the operations proposed by Pá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 the notion of exchange graph of Pál et al. and techniques from the area of parallel machine scheduling.