# American Institute of Mathematical Sciences

doi: 10.3934/jimo.2020056

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

 1 Shenzhen Institutes of Advanced Technology, Chinese Academy of Sciences, Shenzhen 518055, China 2 School of Computer Science and Technology, Shandong Jianzhu University, Jinan 250101, China 3 School of Software, Shandong University, Jinan 250101, China

* Corresponding author: Yong Zhang

Received  October 2019 Revised  November 2019 Published  March 2020

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.

Citation: Yishui Wang, Dongmei Zhang, Peng Zhang, Yong Zhang. Local search algorithm for the squared metric $k$-facility location problem with linear penalties. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2020056
##### References:
 [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [9] D. S. Hochbaum, Heuristics for the fixed cost median problem, Mathematical Programming, 22 (1982), 148-162.  doi: 10.1007/BF01581035.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar

show all references

##### References:
 [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [9] D. S. Hochbaum, Heuristics for the fixed cost median problem, Mathematical Programming, 22 (1982), 148-162.  doi: 10.1007/BF01581035.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar
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
Swap operations (case of $|F|>|F^*|$) for analyzing the upper bound of $C_s + C_p$. The black solid square is a bad facility
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] Gaidi Li, Zhen Wang, Dachuan Xu. An approximation algorithm for the $k$-level facility location problem with submodular penalties. Journal of Industrial & Management Optimization, 2012, 8 (3) : 521-529. doi: 10.3934/jimo.2012.8.521 [2] Jianqin Zhou, Wanquan Liu, Xifeng Wang, Guanglu Zhou. On the $k$-error linear complexity for $p^n$-periodic binary sequences via hypercube theory. Mathematical Foundations of Computing, 2019, 2 (4) : 279-297. doi: 10.3934/mfc.2019018 [3] Silvia Frassu. Nonlinear Dirichlet problem for the nonlocal anisotropic operator $L_K$. Communications on Pure & Applied Analysis, 2019, 18 (4) : 1847-1867. doi: 10.3934/cpaa.2019086 [4] Haisheng Tan, Liuyan Liu, Hongyu Liang. Total $\{k\}$-domination in special graphs. Mathematical Foundations of Computing, 2018, 1 (3) : 255-263. doi: 10.3934/mfc.2018011 [5] Ekta Mittal, Sunil Joshi. Note on a $k$-generalised fractional derivative. Discrete & Continuous Dynamical Systems - S, 2020, 13 (3) : 797-804. doi: 10.3934/dcdss.2020045 [6] Umberto De Maio, Peter I. Kogut, Gabriella Zecca. On optimal $L^1$-control in coefficients for quasi-linear Dirichlet boundary value problems with $BMO$-anisotropic $p$-Laplacian. Mathematical Control & Related Fields, 2019, 0 (0) : 0-0. doi: 10.3934/mcrf.2020021 [7] Gyula Csató. On the isoperimetric problem with perimeter density $r^p$. Communications on Pure & Applied Analysis, 2018, 17 (6) : 2729-2749. doi: 10.3934/cpaa.2018129 [8] Behrad Erfani, Sadoullah Ebrahimnejad, Amirhossein Moosavi. An integrated dynamic facility layout and job shop scheduling problem: A hybrid NSGA-II and local search algorithm. Journal of Industrial & Management Optimization, 2020, 16 (4) : 1801-1834. doi: 10.3934/jimo.2019030 [9] Adam Kanigowski, Federico Rodriguez Hertz, Kurt Vinhage. On the non-equivalence of the Bernoulli and $K$ properties in dimension four. Journal of Modern Dynamics, 2018, 13: 221-250. doi: 10.3934/jmd.2018019 [10] Harbir Antil, Mahamadi Warma. Optimal control of the coefficient for the regional fractional $p$-Laplace equation: Approximation and convergence. Mathematical Control & Related Fields, 2019, 9 (1) : 1-38. doi: 10.3934/mcrf.2019001 [11] Nicholas J. Kass, Mohammad A. Rammaha. Local and global existence of solutions to a strongly damped wave equation of the $p$-Laplacian type. Communications on Pure & Applied Analysis, 2018, 17 (4) : 1449-1478. doi: 10.3934/cpaa.2018070 [12] Gyu Eun Lee. Local wellposedness for the critical nonlinear Schrödinger equation on $\mathbb{T}^3$. Discrete & Continuous Dynamical Systems - A, 2019, 39 (5) : 2763-2783. doi: 10.3934/dcds.2019116 [13] Tuan Anh Dao, Michael Reissig. $L^1$ estimates for oscillating integrals and their applications to semi-linear models with $\sigma$-evolution like structural damping. Discrete & Continuous Dynamical Systems - A, 2019, 39 (9) : 5431-5463. doi: 10.3934/dcds.2019222 [14] Edcarlos D. Silva, José Carlos de Albuquerque, Uberlandio Severo. On a class of linearly coupled systems on $\mathbb{R}^N$ involving asymptotically linear terms. Communications on Pure & Applied Analysis, 2019, 18 (6) : 3089-3101. doi: 10.3934/cpaa.2019138 [15] Hongming Ru, Chunming Tang, Yanfeng Qi, Yuxiao Deng. A construction of $p$-ary linear codes with two or three weights. Advances in Mathematics of Communications, 2019, 0 (0) : 0-0. doi: 10.3934/amc.2020039 [16] Pak Tung Ho. Prescribing $Q$-curvature on $S^n$ in the presence of symmetry. Communications on Pure & Applied Analysis, 2020, 19 (2) : 715-722. doi: 10.3934/cpaa.2020033 [17] Huimin Zheng, Xuejun Guo, Hourong Qin. The Mahler measure of $(x+1/x)(y+1/y)(z+1/z)+\sqrt{k}$. Electronic Research Archive, 2020, 28 (1) : 103-125. doi: 10.3934/era.2020007 [18] Sanjiban Santra. On the positive solutions for a perturbed negative exponent problem on $\mathbb{R}^3$. Discrete & Continuous Dynamical Systems - A, 2018, 38 (3) : 1441-1460. doi: 10.3934/dcds.2018059 [19] VicenŢiu D. RǍdulescu, Somayeh Saiedinezhad. A nonlinear eigenvalue problem with $p(x)$-growth and generalized Robin boundary value condition. Communications on Pure & Applied Analysis, 2018, 17 (1) : 39-52. doi: 10.3934/cpaa.2018003 [20] Shengbing Deng. Construction solutions for Neumann problem with Hénon term in $\mathbb{R}^2$. Discrete & Continuous Dynamical Systems - A, 2019, 39 (4) : 2233-2253. doi: 10.3934/dcds.2019094

2018 Impact Factor: 1.025

## Tools

Article outline

Figures and Tables