RAIRO-Theor. Inf. Appl.
Volume 49, Number 4, October-December 2015
|Page(s)||285 - 306|
|Published online||14 April 2016|
Analysis of a local search algorithm for the k-facility location problem
Department of Computer Science,
Western University, London, Ontario,
Accepted: 25 February 2016
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.
Mathematics Subject Classification: 68W25 / 68W40
Key words: Approximation algorithm / local search / k-facility location
© EDP Sciences 2016
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.