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



[1] |
Gaidi Li, Zhen Wang, Dachuan Xu. An approximation algorithm for the $k$-level facility location problem with submodular penalties. Journal of Industrial and Management Optimization, 2012, 8 (3) : 521-529. doi: 10.3934/jimo.2012.8.521 |
[2] |
Fan Yuan, Dachuan Xu, Donglei Du, Min Li. An exact algorithm for stable instances of the $ k $-means problem with penalties in fixed-dimensional Euclidean space. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021122 |
[3] |
Min Li, Yishui Wang, Dachuan Xu, Dongmei Zhang. The approximation algorithm based on seeding method for functional $ k $-means problem†. Journal of Industrial and Management Optimization, 2022, 18 (1) : 411-426. doi: 10.3934/jimo.2020160 |
[4] |
Chenchen Wu, Wei Lv, Yujie Wang, Dachuan Xu. Approximation algorithm for spherical $ k $-means problem with penalty. Journal of Industrial and Management Optimization, 2022, 18 (4) : 2277-2287. doi: 10.3934/jimo.2021067 |
[5] |
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 |
[6] |
Xavier Gràcia, Xavier Rivas, Narciso Román-Roy. Erratum: Constraint algorithm for singular field theories in the $ k $-cosymplectic framework. Journal of Geometric Mechanics, 2021, 13 (2) : 273-275. doi: 10.3934/jgm.2021007 |
[7] |
Peili Li, Xiliang Lu, Yunhai Xiao. Smoothing Newton method for $ \ell^0 $-$ \ell^2 $ regularized linear inverse problem. Inverse Problems and Imaging, 2022, 16 (1) : 153-177. doi: 10.3934/ipi.2021044 |
[8] |
Silvia Frassu. Nonlinear Dirichlet problem for the nonlocal anisotropic operator $ L_K $. Communications on Pure and Applied Analysis, 2019, 18 (4) : 1847-1867. doi: 10.3934/cpaa.2019086 |
[9] |
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 and Management Optimization, 2020, 16 (4) : 1801-1834. doi: 10.3934/jimo.2019030 |
[10] |
Ekta Mittal, Sunil Joshi. Note on a $ k $-generalised fractional derivative. Discrete and Continuous Dynamical Systems - S, 2020, 13 (3) : 797-804. doi: 10.3934/dcdss.2020045 |
[11] |
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 |
[12] |
Yasemin Cengellenmis, Abdullah Dertli, Steven T. Dougherty, Adrian Korban, Serap Şahinkaya, Deniz Ustun. Reversible $ G $-codes over the ring $ {\mathcal{F}}_{j,k} $ with applications to DNA codes. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021056 |
[13] |
Tian-Xiao He, Peter J.-S. Shiue. Identities for linear recursive sequences of order $ 2 $. Electronic Research Archive, 2021, 29 (5) : 3489-3507. doi: 10.3934/era.2021049 |
[14] |
Zhen-Zhen Tao, Bing Sun. Error estimates for spectral approximation of flow optimal control problem with $ L^2 $-norm control constraint. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022030 |
[15] |
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 |
[16] |
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 and Related Fields, 2020, 10 (4) : 827-854. doi: 10.3934/mcrf.2020021 |
[17] |
Gyula Csató. On the isoperimetric problem with perimeter density $r^p$. Communications on Pure and Applied Analysis, 2018, 17 (6) : 2729-2749. doi: 10.3934/cpaa.2018129 |
[18] |
Lingyan Cheng, Ruinan Li, Liming Wu. Exponential convergence in the Wasserstein metric $ W_1 $ for one dimensional diffusions. Discrete and Continuous Dynamical Systems, 2020, 40 (9) : 5131-5148. doi: 10.3934/dcds.2020222 |
[19] |
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 |
[20] |
Yu-Ming Chu, Saima Rashid, Fahd Jarad, Muhammad Aslam Noor, Humaira Kalsoom. More new results on integral inequalities for generalized $ \mathcal{K} $-fractional conformable Integral operators. Discrete and Continuous Dynamical Systems - S, 2021, 14 (7) : 2119-2135. doi: 10.3934/dcdss.2021063 |
2020 Impact Factor: 1.801
Tools
Metrics
Other articles
by authors
[Back to Top]