# American Institute of Mathematical Sciences

July  2012, 8(3): 521-529. doi: 10.3934/jimo.2012.8.521

## An approximation algorithm for the $k$-level facility location problem with submodular penalties

 1 Department of Applied Mathematics, Beijing University of Technology, 100 Pingleyuan, Chaoyang District, Beijing 100124, China, China 2 Department of Applied Mathematics, Beijing University of Technology, 100 Pingleyuan, Chaoyang District, Beijing, 100124

Received  April 2010 Revised  July 2011 Published  June 2012

In this paper, we consider the $k$-level facility location problem with submodular penalties ($k$-FLPSP). We propose a primal-dual $6$-approximation (combinatorial) algorithm for the $k$-FLPSP.
Citation: Gaidi Li, Zhen Wang, Dachuan Xu. An approximation algorithm for the $k$-level facility location problem with submodular penalties. Journal of Industrial & Management Optimization, 2012, 8 (3) : 521-529. doi: 10.3934/jimo.2012.8.521
##### References:
 [1] K. I. Aardal, F. A. Chudak and D. B. Shmoys, A $3$-approximation algorithm for the $k$-level uncapacitaed facility location problem,, Information Processing Letters, 72 (1999), 161.  doi: 10.1016/S0020-0190(99)00144-1.  Google Scholar [2] A. Ageev, Y. Ye and J. Zhang, Improved combinatorial approximation algorithms for the $k$-level facility location problem,, SIAM Journal on Discrete Mathmatics, 18 (2004), 207.  doi: 10.1137/S0895480102417215.  Google Scholar [3] A. F. Bumb and W. Kern, A simple dual ascent algorithm for the multilevel facility location problem,, in, 2129 (2001), 55.   Google Scholar [4] J. Byrka and K. I. Aardal, An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem,, SIAM Journal on Computing, 39 (2010), 2212.  doi: 10.1137/070708901.  Google Scholar [5] M. Charikar, S. Khuller, D. M. Mount and G. Naraasimban, Algorithms for facility location problems with outliers,, in, (2001), 642.   Google Scholar [6] X. Chen and B. Chen, Approximation algorithms for soft-capacitated facility location in capacitated network design,, Algorithmica, 53 (2009), 263.  doi: 10.1007/s00453-007-9032-7.  Google Scholar [7] F. A. Chudak and K. Nagano, Efficient solutions to relaxations of combinatorial problems with submodular penalties via the Lovász extension and non-smooth convex optimization,, in, (2007), 79.   Google Scholar [8] D. Du, R. Lu and D. Xu, A primal-dual approximation algorithm for the facility location problem with submodular penalties,, Algorithmica, 63 (2012), 191.  doi: 10.1007/s00453-011-9526-1.  Google Scholar [9] L. Fleischer and S. Iwata, A push-relabel framework for submodular function minimization and applications to parametric optimization,, Discrete Applied Mathematics, 131 (2003), 311.  doi: 10.1016/S0166-218X(02)00458-4.  Google Scholar [10] S. Guha and S. Khuller, Greedy strikes back: Improved facility location algorithms,, in, (1998), 649.   Google Scholar [11] A. Hayrapetyan, C. Swamy and E. Tardos, Network design for information networks,, in, (2005), 933.   Google Scholar [12] K. Jain, M. Mahdian, E. Markakis, A. Saberi and V. V. Vazirani, Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP,, Journal of the ACM, 50 (2003), 795.  doi: 10.1145/950620.950621.  Google Scholar [13] K. Jain and V. V. Vazirani, Approximation algorithms for metric facility location and $k$-median probelms using the primal-dual schema and Lagrangian relaxation,, Journal of the ACM, 48 (2001), 274.  doi: 10.1145/375827.375845.  Google Scholar [14] G. Li, Z. Wang and D. Xu, An approximation algorithm for the $k$-level facility location problem with submodular penalties,, in, 12 (2009), 772.   Google Scholar [15] S. Li, A 1.488-approximation algorithm for the uncapacitated facility location problem,, in, 6756 (2011), 77.   Google Scholar [16] M. Mahdian, Y. Ye and J. Zhang, Approximation algorithms for metric facility location problems,, SIAM Journal on Computing, 36 (2006), 411.  doi: 10.1137/S0097539703435716.  Google Scholar [17] J. Shu, An efficient greedy heuristic for warehouse-retailer network design optimization,, Transportation Science, 44 (2010), 183.  doi: 10.1287/trsc.1090.0302.  Google Scholar [18] J. Shu, Q. Ma and S. Li, Integrated location and two-echelon inventory network design under uncertainty,, Annals of Operations Research, 181 (2010), 233.  doi: 10.1007/s10479-010-0732-z.  Google Scholar [19] J. Shu, C.-P. Teo and Z.-J. Max Shen, Stochastic transportation-inventory network design problem,, Operations Research, 53 (2005), 48.  doi: 10.1287/opre.1040.0140.  Google Scholar [20] D. B. Shmoys, E. Tardos and K. I. Aardal, Approximation algorithms for facility location problems (extended abstract),, Proceedings of STOC, (1997), 265.   Google Scholar [21] G. Xu and J. Xu, An LP rounding algorithm for approximating uncapacitated facility location problem with penalties,, Information Processing Letters, 94 (2005), 119.  doi: 10.1016/j.ipl.2005.01.005.  Google Scholar [22] G. Xu and J. Xu, An improved approximation algorithm for uncapacitated facility location problem with penalties,, Journal of Combinatorial Optimization, 17 (2009), 424.  doi: 10.1007/s10878-007-9127-8.  Google Scholar [23] J. Zhang, Approximating the two-level facility location problem via a quasi-greedy approach,, Mathematical Programming, 108 (2006), 159.  doi: 10.1007/s10107-006-0704-x.  Google Scholar [24] J. Zhang, B. Chen and Y. Ye, A multiexchange local search algorithm for the capacitated facility location problem,, Mathematics of Operations Research, 30 (2005), 389.  doi: 10.1287/moor.1040.0125.  Google Scholar [25] L. Zhang and S.-Y. Wu, Robust solutions to Euclidean facility location problems with uncertain data,, Journal of Industrial and Management Optimization, 6 (2010), 751.   Google Scholar [26] P. Zhang, A new approximation algorithm for the $k$-facility location problem,, Theoretical Computer Science, 384 (2007), 126.  doi: 10.1016/j.tcs.2007.05.024.  Google Scholar

show all references

##### References:
 [1] K. I. Aardal, F. A. Chudak and D. B. Shmoys, A $3$-approximation algorithm for the $k$-level uncapacitaed facility location problem,, Information Processing Letters, 72 (1999), 161.  doi: 10.1016/S0020-0190(99)00144-1.  Google Scholar [2] A. Ageev, Y. Ye and J. Zhang, Improved combinatorial approximation algorithms for the $k$-level facility location problem,, SIAM Journal on Discrete Mathmatics, 18 (2004), 207.  doi: 10.1137/S0895480102417215.  Google Scholar [3] A. F. Bumb and W. Kern, A simple dual ascent algorithm for the multilevel facility location problem,, in, 2129 (2001), 55.   Google Scholar [4] J. Byrka and K. I. Aardal, An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem,, SIAM Journal on Computing, 39 (2010), 2212.  doi: 10.1137/070708901.  Google Scholar [5] M. Charikar, S. Khuller, D. M. Mount and G. Naraasimban, Algorithms for facility location problems with outliers,, in, (2001), 642.   Google Scholar [6] X. Chen and B. Chen, Approximation algorithms for soft-capacitated facility location in capacitated network design,, Algorithmica, 53 (2009), 263.  doi: 10.1007/s00453-007-9032-7.  Google Scholar [7] F. A. Chudak and K. Nagano, Efficient solutions to relaxations of combinatorial problems with submodular penalties via the Lovász extension and non-smooth convex optimization,, in, (2007), 79.   Google Scholar [8] D. Du, R. Lu and D. Xu, A primal-dual approximation algorithm for the facility location problem with submodular penalties,, Algorithmica, 63 (2012), 191.  doi: 10.1007/s00453-011-9526-1.  Google Scholar [9] L. Fleischer and S. Iwata, A push-relabel framework for submodular function minimization and applications to parametric optimization,, Discrete Applied Mathematics, 131 (2003), 311.  doi: 10.1016/S0166-218X(02)00458-4.  Google Scholar [10] S. Guha and S. Khuller, Greedy strikes back: Improved facility location algorithms,, in, (1998), 649.   Google Scholar [11] A. Hayrapetyan, C. Swamy and E. Tardos, Network design for information networks,, in, (2005), 933.   Google Scholar [12] K. Jain, M. Mahdian, E. Markakis, A. Saberi and V. V. Vazirani, Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP,, Journal of the ACM, 50 (2003), 795.  doi: 10.1145/950620.950621.  Google Scholar [13] K. Jain and V. V. Vazirani, Approximation algorithms for metric facility location and $k$-median probelms using the primal-dual schema and Lagrangian relaxation,, Journal of the ACM, 48 (2001), 274.  doi: 10.1145/375827.375845.  Google Scholar [14] G. Li, Z. Wang and D. Xu, An approximation algorithm for the $k$-level facility location problem with submodular penalties,, in, 12 (2009), 772.   Google Scholar [15] S. Li, A 1.488-approximation algorithm for the uncapacitated facility location problem,, in, 6756 (2011), 77.   Google Scholar [16] M. Mahdian, Y. Ye and J. Zhang, Approximation algorithms for metric facility location problems,, SIAM Journal on Computing, 36 (2006), 411.  doi: 10.1137/S0097539703435716.  Google Scholar [17] J. Shu, An efficient greedy heuristic for warehouse-retailer network design optimization,, Transportation Science, 44 (2010), 183.  doi: 10.1287/trsc.1090.0302.  Google Scholar [18] J. Shu, Q. Ma and S. Li, Integrated location and two-echelon inventory network design under uncertainty,, Annals of Operations Research, 181 (2010), 233.  doi: 10.1007/s10479-010-0732-z.  Google Scholar [19] J. Shu, C.-P. Teo and Z.-J. Max Shen, Stochastic transportation-inventory network design problem,, Operations Research, 53 (2005), 48.  doi: 10.1287/opre.1040.0140.  Google Scholar [20] D. B. Shmoys, E. Tardos and K. I. Aardal, Approximation algorithms for facility location problems (extended abstract),, Proceedings of STOC, (1997), 265.   Google Scholar [21] G. Xu and J. Xu, An LP rounding algorithm for approximating uncapacitated facility location problem with penalties,, Information Processing Letters, 94 (2005), 119.  doi: 10.1016/j.ipl.2005.01.005.  Google Scholar [22] G. Xu and J. Xu, An improved approximation algorithm for uncapacitated facility location problem with penalties,, Journal of Combinatorial Optimization, 17 (2009), 424.  doi: 10.1007/s10878-007-9127-8.  Google Scholar [23] J. Zhang, Approximating the two-level facility location problem via a quasi-greedy approach,, Mathematical Programming, 108 (2006), 159.  doi: 10.1007/s10107-006-0704-x.  Google Scholar [24] J. Zhang, B. Chen and Y. Ye, A multiexchange local search algorithm for the capacitated facility location problem,, Mathematics of Operations Research, 30 (2005), 389.  doi: 10.1287/moor.1040.0125.  Google Scholar [25] L. Zhang and S.-Y. Wu, Robust solutions to Euclidean facility location problems with uncertain data,, Journal of Industrial and Management Optimization, 6 (2010), 751.   Google Scholar [26] P. Zhang, A new approximation algorithm for the $k$-facility location problem,, Theoretical Computer Science, 384 (2007), 126.  doi: 10.1016/j.tcs.2007.05.024.  Google Scholar
 [1] Wolfgang Riedl, Robert Baier, Matthias Gerdts. Optimization-based subdivision algorithm for reachable sets. Journal of Computational Dynamics, 2021, 8 (1) : 99-130. doi: 10.3934/jcd.2021005 [2] Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017 [3] Cheng Peng, Zhaohui Tang, Weihua Gui, Qing Chen, Jing He. A bidirectional weighted boundary distance algorithm for time series similarity computation based on optimized sliding window size. Journal of Industrial & Management Optimization, 2021, 17 (1) : 205-220. doi: 10.3934/jimo.2019107 [4] Shun Zhang, Jianlin Jiang, Su Zhang, Yibing Lv, Yuzhen Guo. ADMM-type methods for generalized multi-facility Weber problem. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020171 [5] Yifan Chen, Thomas Y. Hou. Function approximation via the subsampled Poincaré inequality. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 169-199. doi: 10.3934/dcds.2020296 [6] Mostafa Mbekhta. Representation and approximation of the polar factor of an operator on a Hilbert space. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020463 [7] Zonghong Cao, Jie Min. Selection and impact of decision mode of encroachment and retail service in a dual-channel supply chain. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020167 [8] Manuel Friedrich, Martin Kružík, Jan Valdman. Numerical approximation of von Kármán viscoelastic plates. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 299-319. doi: 10.3934/dcdss.2020322 [9] Pierluigi Colli, Gianni Gilardi, Jürgen Sprekels. Deep quench approximation and optimal control of general Cahn–Hilliard systems with fractional operators and double obstacle potentials. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 243-271. doi: 10.3934/dcdss.2020213

2019 Impact Factor: 1.366