# American Institute of Mathematical Sciences

• Previous Article
Selecting the supply chain financing mode under price-sensitive demand: Confirmed warehouse financing vs. trade credit
• JIMO Home
• This Issue
• Next Article
Optimal maximally decimated M-channel mirrored paraunitary linear phase FIR filter bank design via norm relaxed sequential quadratic programming
July  2021, 17(4): 2013-2030. 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, 2021, 17 (4) : 2013-2030. 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] Jong Yoon Hyun, Yoonjin Lee, Yansheng Wu. Connection of $p$-ary $t$-weight linear codes to Ramanujan Cayley graphs with $t+1$ eigenvalues. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020133 [2] Xiaoni Chi, Zhongping Wan, Zijun Hao. A full-modified-Newton step $O(n)$ infeasible interior-point method for the special weighted linear complementarity problem. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021082 [3] Ahmad El Hajj, Hassan Ibrahim, Vivian Rizik. $BV$ solution for a non-linear Hamilton-Jacobi system. Discrete & Continuous Dynamical Systems, 2021, 41 (7) : 3273-3293. doi: 10.3934/dcds.2020405 [4] Alfonso Castro, Jorge Cossio, Sigifredo Herrón, Carlos Vélez. Infinitely many radial solutions for a $p$-Laplacian problem with indefinite weight. Discrete & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021058 [5] Jennifer D. Key, Bernardo G. Rodrigues. Binary codes from $m$-ary $n$-cubes $Q^m_n$. Advances in Mathematics of Communications, 2021, 15 (3) : 507-524. doi: 10.3934/amc.2020079 [6] Chaoqian Li, Yajun Liu, Yaotang Li. Note on $Z$-eigenvalue inclusion theorems for tensors. Journal of Industrial & Management Optimization, 2021, 17 (2) : 687-693. doi: 10.3934/jimo.2019129 [7] Gbeminiyi John Oyewole, Olufemi Adetunji. Solving the facility location and fixed charge solid transportation problem. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1557-1575. doi: 10.3934/jimo.2020034 [8] Dean Crnković, Nina Mostarac, Bernardo G. Rodrigues, Leo Storme. $s$-PD-sets for codes from projective planes $\mathrm{PG}(2,2^h)$, $5 \leq h\leq 9$. Advances in Mathematics of Communications, 2021, 15 (3) : 423-440. doi: 10.3934/amc.2020075 [9] Lei Liu, Li Wu. Multiplicity of closed characteristics on $P$-symmetric compact convex hypersurfaces in $\mathbb{R}^{2n}$. Discrete & Continuous Dynamical Systems, 2021, 41 (6) : 2635-3652. doi: 10.3934/dcds.2020378 [10] Shihu Li, Wei Liu, Yingchao Xie. Large deviations for stochastic 3D Leray-$\alpha$ model with fractional dissipation. Communications on Pure & Applied Analysis, 2019, 18 (5) : 2491-2509. doi: 10.3934/cpaa.2019113 [11] Emma D'Aniello, Saber Elaydi. The structure of $\omega$-limit sets of asymptotically non-autonomous discrete dynamical systems. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 903-915. doi: 10.3934/dcdsb.2019195 [12] Denis Bonheure, Silvia Cingolani, Simone Secchi. Concentration phenomena for the Schrödinger-Poisson system in $\mathbb{R}^2$. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : 1631-1648. doi: 10.3934/dcdss.2020447 [13] Raj Kumar, Maheshanand Bhaintwal. Duadic codes over $\mathbb{Z}_4+u\mathbb{Z}_4$. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020135 [14] Brian Ryals, Robert J. Sacker. Bifurcation in the almost periodic $2$D Ricker map. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021089 [15] Zhaoxia Wang, Hebai Chen. A nonsmooth van der Pol-Duffing oscillator (I): The sum of indices of equilibria is $-1$. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021096 [16] Zhaoxia Wang, Hebai Chen. A nonsmooth van der Pol-Duffing oscillator (II): The sum of indices of equilibria is $1$. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021101 [17] Said Taarabti. Positive solutions for the $p(x)-$Laplacian : Application of the Nehari method. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021029 [18] Khalid Latrach, Hssaine Oummi, Ahmed Zeghal. Existence results for nonlinear mono-energetic singular transport equations: $L^p$-spaces. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021028 [19] Yao Nie, Jia Yuan. The Littlewood-Paley $pth$-order moments in three-dimensional MHD turbulence. Discrete & Continuous Dynamical Systems, 2021, 41 (7) : 3045-3062. doi: 10.3934/dcds.2020397 [20] Raffaele Folino, Ramón G. Plaza, Marta Strani. Long time dynamics of solutions to $p$-Laplacian diffusion problems with bistable reaction terms. Discrete & Continuous Dynamical Systems, 2021, 41 (7) : 3211-3240. doi: 10.3934/dcds.2020403

2019 Impact Factor: 1.366