
-
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] |
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
Tools
Article outline
Figures and Tables
[Back to Top]