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

Yishui Wang; Dongmei Zhang; Peng Zhang; Yong Zhang

doi:10.3934/jimo.2020056

Article Contents

2021, Volume 17, Issue 4: 2013-2030. Doi: 10.3934/jimo.2020056

This issue Previous Article Optimal maximally decimated M-channel mirrored paraunitary linear phase FIR filter bank design via norm relaxed sequential quadratic programming Next Article Selecting the supply chain financing mode under price-sensitive demand: Confirmed warehouse financing vs. trade credit

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
^* Corresponding author: Yong Zhang

Received: September 30, 2019

Revised: October 31, 2019

Early access: March 2020

Published: July 2021

Abstract Full Text(HTML) Figure(3) Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 90B80.

Citation:

FullText(HTML)

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

Download: Full-size image 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

Download: Full-size image 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) $

Download: Full-size image PowerPoint slide

Related Papers

Cited by

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.
[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.