Analysis of a local search algorithm for the $k$-facility location problem

Samei, Nasim ; Solis-Oba, Roberto

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 49 (2015) no. 4, pp. 285-306

Résumé

In the $k$-facility location problem we are given the possible locations for a group of at most $k$ facilities that are to provide some service to a set of clients. Each location has an associated cost for building a facility there. The goal is to select the locations for the facilities that minimize the sum of the cost for building the facilities and the total cost for servicing the clients. In this paper we analyse a local-search heuristic with multiple swaps for the metric $k$-facility location problem and prove that it has locality gap of 2 + √3+ ε for any constant $ϵ>0$. This matches the bound obtained by Zhang [Theoret. Comput. Sci. 384 (2007) 126–135.] for a local search algorithm that uses insertions and deletions in addition to swaps. We also prove a second, tight, bound for the locality gap of our algorithm which is better than the above one in many cases. For example, when the ratio between the highest and lowest facility cost is bounded by $p+1$, where $p$ is the maximum number of facilities that can be exchanged in a swap operation, the locality of our algorithm is 3 + 2/p; this matches the locality gap of the algorithm of Arya et al. [SIAM J. Comput. 33 (2004) 544–562.] for the $k$-median problem.

Détail

DOI : 10.1051/ita/2016002

Classification : 68W25, 68W40
Keywords: Approximation algorithm, local search, k-facility location