Algorithm for the Capacitated Facility Location Problem

What is it about?

We present a multi-exchange local search algorithm for approximating the capacitated facility location problem, 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 in the interval centred at 3+ 2√2 of arbitrarily small length. 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.

Featured Image