Article Contents
Article Contents

# Local search algorithm for the squared metric $k$-facility location problem with linear penalties

• * Corresponding author: Yong Zhang
• In the $k$-facility location problem, an important combinatorial optimization problem combining the classical facility location and $k$-median problems, we are given the locations of some facilities and clients, and need to open at most $k$ facilities and connect all clients to opened facilities, minimizing the facility opening and connection cost. This paper considers the squared metric $k$-facility location problem with linear penalties, a robust version of the $k$-facility location problem. In this problem, we do not have to connect all clients to facilities, but each client that is not served by any facility must pay a penalty cost. The connection costs of facilities and clients are supposed to be squared metric, which is more general than the metric case. We provide a constant approximation algorithm based on the local search scheme with add, drop, and swap operations for this problem. Furthermore, we improve the approximation ratio by using the scaling technique.

Mathematics Subject Classification: Primary: 90B80.

 Citation:

• Figure 1.  Partitions and local operations of $F$ and $F^*$ for analyzing the upper bound of $C_f + C_p$. The black solid squares represent all bad facilities. Each gray solid square represents the nearest facility among a part of $F^*$ to the bad facility capturing them

Figure 3.  Swap operations (case of $|F|>|F^*|$) for analyzing the upper bound of $C_s + C_p$. The black solid square is a bad facility

Figure 2.  Different cases (partition of $N_F(a^l_i) \cup N_F^*(b^l_i)$) for analyzing the new cost after the operation $swap(a^l_i, b^l_i)$

•  [1] V. Arya, N. Garg, R. Khandekar, A. Meyerson, K. Munagala and V. Pandit, Local search heuristics for $k$-median and facility location problems, SIAM Journal on Computing, 33 (2004), 544-562.  doi: 10.1137/S0097539702416402. [2] J. Byrka, T. Pensyl, B. Rybicki, A. Srinivasan and K. Trinh, An improved approximation for $k$-median and positive correlation in budgeted optimization, ACM Transactions on Algorithms, 13 (2017), Art. 23, 31 pp. doi: 10.1145/2981561. [3] M. Charikar and S. Guha, Improved combinatorial algorithms for facility location problems, SIAM Journal on Computing, 34 (2005), 803-824.  doi: 10.1137/S0097539701398594. [4] M. Charikar, S. Guha, É. Tardos and D. B. Shmoys, A constant-factor approximation algorithm for the $k$-median problem, Annual ACM Symposium on Theory of Computing (Atlanta, GA, 1999), ACM, New York, (1999), 1–10. doi: 10.1145/301250.301257. [5] M. Charikar, S. Khuller, D. M. Mount and G. Narasimhan, Algorithms for facility location problems with outliers, Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, PA, (2001), 642–651. [6] F. A. Chudak and D. B. Shmoys, Improved approximation algorithms for the uncapacitated facility location problem, SIAM Journal on Computing, 33 (2003), 1-25.  doi: 10.1137/S0097539703405754. [7] C. G. Fernandes, L. A. A. Meira, F. K. Miyazawa and L. L. C. Pedrosa, A systematic approach to bound factor-revealing LPs and its application to the metric and squared metric facility location problems, Mathematical Programming, 153 (2015), 655-685.  doi: 10.1007/s10107-014-0821-x. [8] M. Hajiaghayi, R. Khandekar and G. Kortsarz, Local search algorithms for the red-blue median problem, Algorithmica, 63 (2012), 795-814.  doi: 10.1007/s00453-011-9547-9. [9] D. S. Hochbaum, Heuristics for the fixed cost median problem, Mathematical Programming, 22 (1982), 148-162.  doi: 10.1007/BF01581035. [10] K. Jain and V. V. Vazirani, Approximation algorithms for metric facility location and $k$-median problems using the primal-dual schema and Lagrangian relaxation, Journal of the ACM, 48 (2001), 274-296.  doi: 10.1145/375827.375845. [11] S. Li, A 1.488 approximation algorithm for the uncapacitated facility location problem, Information and Computation, 222 (2013), 45-58.  doi: 10.1016/j.ic.2012.01.007. [12] Y. Li, D. L. Du, N. H. Xiu and D. C. Xu, Improved approximation algorithms for the facility location problems with linear/submodular penalties, Algorithmica, 73 (2015), 460-482.  doi: 10.1007/s00453-014-9911-7. [13] D. B. Shmoys, É. Tardos, and K. Aardal, Approximation algorithms for facility location problems, Proceedings of the 29th Annual ACM Symposium on Theory of Computing, ACM, New York, NY, (1997), 265–274. doi: 10.1145/258533.258600. [14] Y. S. Wang, D. C. Xu, D. L. Du and C. C. Wu, An approximation algorithm for the nth power metric facility location problem with linear penalties, Optimization Letters, 11 (2017), 983-993.  doi: 10.1007/s11590-015-0989-x. [15] Y. S. Wang, D. C. Xu, D. L. Du and C. C. Wu, An approximation algorithm for $k$-facility location problem with linear penalties using local search scheme, Journal of Combinatorial Optimization, 36 (2018), 264-279.  doi: 10.1007/s10878-016-0080-2. [16] Y. C. Xu, D. C. Xu, D. L. Du and D. M. Zhang, Approximation algorithm for squared metric facility location problem with nonuniform capacities, Discrete Applied Mathematics, 264 (2019), 208-217.  doi: 10.1016/j.dam.2019.03.013. [17] Y. C. Xu, D. C. Xu, D. L. Du and C. C. Wu, Local search algorithm for universal facility location problem with linear penalties, Journal of Global Optimization, 67 (2017), 367-378.  doi: 10.1007/s10898-015-0394-0. [18] P. Zhang, A new approximation algorithm for the $k$-facility location problem, Theoretical Computer Science, 384 (2007), 126-135.  doi: 10.1016/j.tcs.2007.05.024. [19] D. M. Zhang, D. C. Xu, Y. S. Wang, P. Zhang and Z. N. Zhang, Local search approximation algorithms for the sum of squares facility location problems, Journal of Global Optimization, 74 (2019), 909-932.  doi: 10.1007/s10898-018-00733-2. [20] D. M. Zhang, D. C. Xu, Y. S. Wang, P. Zhang and Z. N. Zhang, A local search approximation algorithm for a squared metric $k$-facility location problem, Journal of Combinatorial Optimization, 35 (2018), 1168-1184.  doi: 10.1007/s10878-018-0261-2.

Figures(3)