In the
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 = {https://www.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 - https://www.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 https://www.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. https://www.numdam.org/articles/10.1051/ita/2016002/
Local search heuristic for
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 :