In the -facility location problem we are given the possible locations for a group of at most 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 -facility location problem and prove that it has locality gap of 2 + √3+ ε for any constant . 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 , where 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 -median problem.
Mots-clés : Approximation algorithm, local search, k-facility location
@article{ITA_2015__49_4_285_0, author = {Samei, Nasim and Solis-Oba, Roberto}, title = {Analysis of a local search algorithm for the $k$-facility location problem}, journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications}, pages = {285--306}, publisher = {EDP-Sciences}, volume = {49}, number = {4}, year = {2015}, doi = {10.1051/ita/2016002}, mrnumber = {3507248}, zbl = {1372.68316}, language = {en}, url = {http://archive.numdam.org/articles/10.1051/ita/2016002/} }
TY - JOUR AU - Samei, Nasim AU - Solis-Oba, Roberto TI - Analysis of a local search algorithm for the $k$-facility location problem JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2015 SP - 285 EP - 306 VL - 49 IS - 4 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ita/2016002/ DO - 10.1051/ita/2016002 LA - en ID - ITA_2015__49_4_285_0 ER -
%0 Journal Article %A Samei, Nasim %A Solis-Oba, Roberto %T Analysis of a local search algorithm for the $k$-facility location problem %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2015 %P 285-306 %V 49 %N 4 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ita/2016002/ %R 10.1051/ita/2016002 %G en %F ITA_2015__49_4_285_0
Samei, Nasim; Solis-Oba, Roberto. Analysis of a local search algorithm for the $k$-facility location problem. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 49 (2015) no. 4, pp. 285-306. doi : 10.1051/ita/2016002. http://archive.numdam.org/articles/10.1051/ita/2016002/
Local search heuristic for -median and facility location problem. SIAM J. Comput. 33 (2004) 544–562. | DOI | MR | Zbl
, , , , and ,N. Atay and B. Bayazit, Mobile Wireless Sensor Network Connectivity Repair with K-Redundancy. Algorithmic Foundations of Robotics, edited by G.S. Chirikjian, H. Choset, M. Morales and T. Murphey. Springer Tracts Adv. Rob. (2010) 35–52. | Zbl
Improved Combinatorial Algorithms for Facility Location Problems. SIAM J. Comput. 34 (2005) 803–824. | DOI | MR | Zbl
and ,A constant-factor approximation algorithm for the k-median problem. J. Comput. Syst. Sci. 65 (2002) 129–149. | DOI | MR | Zbl
, , and ,Exceptional paper-location of bank accounts to optimize float: An analytic study of exact and approximate algorithm. Manage. Sci. 23 (1977) 789–810. | DOI | MR | Zbl
, and ,A. Gupta and K. Tangwongsan, Simpler Analyses of Local Search Algorithms for Facility Location. Preprint arXiv:0809.2554 (2008).
Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation. J. ACM 48 (2001) 274–296. | DOI | MR | Zbl
and ,Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. J. ACM 50 (2003) 795–824. | DOI | MR | Zbl
, , , and ,Facility location models for distribution system design. Eur. J. Oper. Res. 162 (2005) 4-29. | DOI | MR | Zbl
and ,A 1.488 approximation algorithm for the uncapacitated facility location problem. Inf. Comput. 222 (2013) 45–58. | DOI | MR | Zbl
,L. Qiu, V. Padmanabhan and G. Voelker, On the Placement of Web Server Replicas, in Proc. of IEEE INFOCOM01 (2001) 1587–1596.
D. Shmoys, E. Tardos and K. Aardal, Approximation Algorithms for Facility Location Problems, in Proc. of the 29th Annual ACM Symposium on Theory of Computing ACM. New York (1997) 265–274. | Zbl
A new approximation algorithm for the k-facility location problem. Theoret. Comput. Sci. 384 (2007) 126–135. | DOI | MR | Zbl
,Cité par Sources :