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.

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.

Classification : 68W25, 68W40
Mots clés : Approximation algorithm, local search, k-facility location

V. Arya, N. Garg, R. Khandekar, A. Meyerson, K. Munagala and V. Pandit, Local search heuristic for $k$-median and facility location problem. SIAM J. Comput. 33 (2004) 544–562. | DOI | MR | Zbl

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

M. Charikar and S. Guha, Improved Combinatorial Algorithms for Facility Location Problems. SIAM J. Comput. 34 (2005) 803–824. | DOI | MR | Zbl

M. Charikar, S. Guha, E. Tardos and D. Shmoys, A constant-factor approximation algorithm for the k-median problem. J. Comput. Syst. Sci. 65 (2002) 129–149. | DOI | MR | Zbl

G. Cornuejols, M.L. Fisher and G.L. Nemhauser, 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

A. Gupta and K. Tangwongsan, Simpler Analyses of Local Search Algorithms for Facility Location. Preprint arXiv:0809.2554 (2008).

K. Jain and V. Vazirani, 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

K. Jain, M. Mahdian, E. Markakis, A. Saberi and V. Vazirani, Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. J. ACM 50 (2003) 795–824. | DOI | MR | Zbl

A. Klose and A. Drexl, Facility location models for distribution system design. Eur. J. Oper. Res. 162 (2005) 4-29. | DOI | MR | Zbl

S. Li, 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

P. Zhang, A new approximation algorithm for the k-facility location problem. Theoret. Comput. Sci. 384 (2007) 126–135. | DOI | MR | Zbl