American Institute of Mathematical Sciences

• Previous Article
The joint location-transportation model based on grey bi-level programming for early post-earthquake relief
• JIMO Home
• This Issue
• Next Article
Two-period pricing and ordering decisions of perishable products with a learning period for demand disruption
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] 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 [2] Lei Liu, Li Wu. Multiplicity of closed characteristics on $P$-symmetric compact convex hypersurfaces in $\mathbb{R}^{2n}$. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020378 [3] 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 [4] 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 [5] Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399 [6] Jon Aaronson, Dalia Terhesiu. Local limit theorems for suspended semiflows. Discrete & Continuous Dynamical Systems - A, 2020, 40 (12) : 6575-6609. doi: 10.3934/dcds.2020294 [7] J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008 [8] Demetres D. Kouvatsos, Jumma S. Alanazi, Kevin Smith. A unified ME algorithm for arbitrary open QNMs with mixed blocking mechanisms. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 781-816. doi: 10.3934/naco.2011.1.781 [9] Seung-Yeal Ha, Shi Jin. Local sensitivity analysis for the Cucker-Smale model with random inputs. Kinetic & Related Models, 2018, 11 (4) : 859-889. doi: 10.3934/krm.2018034 [10] Zhihua Zhang, Naoki Saito. PHLST with adaptive tiling and its application to antarctic remote sensing image approximation. Inverse Problems & Imaging, 2014, 8 (1) : 321-337. doi: 10.3934/ipi.2014.8.321 [11] Xianming Liu, Guangyue Han. A Wong-Zakai approximation of stochastic differential equations driven by a general semimartingale. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2499-2508. doi: 10.3934/dcdsb.2020192 [12] Enkhbat Rentsen, Battur Gompil. Generalized nash equilibrium problem based on malfatti's problem. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 209-220. doi: 10.3934/naco.2020022 [13] Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021 [14] Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271 [15] Diana Keller. Optimal control of a linear stochastic Schrödinger equation. Conference Publications, 2013, 2013 (special) : 437-446. doi: 10.3934/proc.2013.2013.437 [16] Guillaume Bal, Wenjia Jing. Homogenization and corrector theory for linear transport in random media. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1311-1343. doi: 10.3934/dcds.2010.28.1311 [17] Nizami A. Gasilov. Solving a system of linear differential equations with interval coefficients. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2739-2747. doi: 10.3934/dcdsb.2020203 [18] Ka Luen Cheung, Man Chun Leung. Asymptotic behavior of positive solutions of the equation $\Delta u + K u^{\frac{n+2}{n-2}} = 0$ in $IR^n$ and positive scalar curvature. Conference Publications, 2001, 2001 (Special) : 109-120. doi: 10.3934/proc.2001.2001.109 [19] Hildeberto E. Cabral, Zhihong Xia. Subharmonic solutions in the restricted three-body problem. Discrete & Continuous Dynamical Systems - A, 1995, 1 (4) : 463-474. doi: 10.3934/dcds.1995.1.463 [20] Zhiming Guo, Zhi-Chun Yang, Xingfu Zou. Existence and uniqueness of positive solution to a non-local differential equation with homogeneous Dirichlet boundary condition---A non-monotone case. Communications on Pure & Applied Analysis, 2012, 11 (5) : 1825-1838. doi: 10.3934/cpaa.2012.11.1825

2019 Impact Factor: 1.366

Metrics

• PDF downloads (78)
• HTML views (404)
• Cited by (0)

Other articlesby authors

• on AIMS
• on Google Scholar

[Back to Top]