American Institute of Mathematical Sciences

Advanced
  • 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

Yishui Wang 1, , Dongmei Zhang 2, , Peng Zhang 3, and  Yong Zhang 1,,

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.

Keywords: Approximation algorithm, local search, $ k $-facility location problem, linear penalties, squared metric.
Mathematics Subject Classification: Primary: 90B80.
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

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 Options

Download full-size image

Download as PowerPoint slide

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 Options

Download full-size image

Download as PowerPoint slide

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) $
Figure Options

Download full-size image

Download as PowerPoint slide

[1]

Ahmad El Hajj, Hassan Ibrahim, Vivian Rizik. $ BV $ solution for a non-linear Hamilton-Jacobi system. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020405
[2]

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, 2021, 15 (1) : 9-22. doi: 10.3934/amc.2020039
[3]

Shahede Omidi, Jafar Fathali. Inverse single facility location problem on a tree with balancing on the distance of server to clients. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021017
[4]

Federico Rodriguez Hertz, Zhiren Wang. On $ \epsilon $-escaping trajectories in homogeneous spaces. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 329-357. doi: 10.3934/dcds.2020365
[5]

Martin Heida, Stefan Neukamm, Mario Varga. Stochastic homogenization of $ \Lambda $-convex gradient flows. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 427-453. doi: 10.3934/dcdss.2020328
[6]

Jiahao Qiu, Jianjie Zhao. Maximal factors of order $ d $ of dynamical cubespaces. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 601-620. doi: 10.3934/dcds.2020278
[7]

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
[8]

Mathew Gluck. Classification of solutions to a system of $ n^{\rm th} $ order equations on $ \mathbb R^n $. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5413-5436. doi: 10.3934/cpaa.2020246
[9]

Luca Battaglia, Francesca Gladiali, Massimo Grossi. Asymptotic behavior of minimal solutions of $ -\Delta u = \lambda f(u) $ as $ \lambda\to-\infty $. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 681-700. doi: 10.3934/dcds.2020293
[10]

Guoyuan Chen, Yong Liu, Juncheng Wei. Nondegeneracy of harmonic maps from $ {{\mathbb{R}}^{2}} $ to $ {{\mathbb{S}}^{2}} $. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3215-3233. doi: 10.3934/dcds.2019228
[11]

Magdalena Foryś-Krawiec, Jiří Kupka, Piotr Oprocha, Xueting Tian. On entropy of $ \Phi $-irregular and $ \Phi $-level sets in maps with the shadowing property. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1271-1296. doi: 10.3934/dcds.2020317
[12]

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
[13]

Wenqiang Zhao, Yijin Zhang. High-order Wong-Zakai approximations for non-autonomous stochastic $ p $-Laplacian equations on $ \mathbb{R}^N $. Communications on Pure & Applied Analysis, 2021, 20 (1) : 243-280. doi: 10.3934/cpaa.2020265
[14]

Yuan Cao, Yonglin Cao, Hai Q. Dinh, Ramakrishna Bandi, Fang-Wei Fu. An explicit representation and enumeration for negacyclic codes of length $ 2^kn $ over $ \mathbb{Z}_4+u\mathbb{Z}_4 $. Advances in Mathematics of Communications, 2021, 15 (2) : 291-309. doi: 10.3934/amc.2020067
[15]

Hai Q. Dinh, Bac T. Nguyen, Paravee Maneejuk. Constacyclic codes of length $ 8p^s $ over $ \mathbb F_{p^m} + u\mathbb F_{p^m} $. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020123
[16]

Yichen Zhang, Meiqiang Feng. A coupled $ p $-Laplacian elliptic system: Existence, uniqueness and asymptotic behavior. Electronic Research Archive, 2020, 28 (4) : 1419-1438. doi: 10.3934/era.2020075
[17]

Aihua Fan, Jörg Schmeling, Weixiao Shen. $ L^\infty $-estimation of generalized Thue-Morse trigonometric polynomials and ergodic maximization. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 297-327. doi: 10.3934/dcds.2020363
[18]

Denis Bonheure, Silvia Cingolani, Simone Secchi. Concentration phenomena for the Schrödinger-Poisson system in $ \mathbb{R}^2 $. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020447
[19]

Lihong Zhang, Wenwen Hou, Bashir Ahmad, Guotao Wang. Radial symmetry for logarithmic Choquard equation involving a generalized tempered fractional $ p $-Laplacian. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020445
[20]

Mokhtar Bouloudene, Manar A. Alqudah, Fahd Jarad, Yassine Adjabi, Thabet Abdeljawad. Nonlinear singular $ p $ -Laplacian boundary value problems in the frame of conformable derivative. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020442

2019 Impact Factor: 1.366

Tools

Article outline

Figures and Tables

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences