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] Fengmin Wang, Dachuan Xu, Donglei Du, Chenchen Wu. Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 91-100. doi: 10.3934/naco.2015.5.91 [2] Gianni Di Pillo, Giampaolo Liuzzi, Stefano Lucidi. A primal-dual algorithm for nonlinear programming exploiting negative curvature directions. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 509-528. doi: 10.3934/naco.2011.1.509 [3] Xiaojing Ye, Haomin Zhou. Fast total variation wavelet inpainting via approximated primal-dual hybrid gradient algorithm. Inverse Problems & Imaging, 2013, 7 (3) : 1031-1050. doi: 10.3934/ipi.2013.7.1031 [4] Jen-Yen Lin, Hui-Ju Chen, Ruey-Lin Sheu. Augmented Lagrange primal-dual approach for generalized fractional programming problems. Journal of Industrial & Management Optimization, 2013, 9 (4) : 723-741. doi: 10.3934/jimo.2013.9.723 [5] Yanqin Bai, Xuerui Gao, Guoqiang Wang. Primal-dual interior-point algorithms for convex quadratic circular cone optimization. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 211-231. doi: 10.3934/naco.2015.5.211 [6] Siqi Li, Weiyi Qian. Analysis of complexity of primal-dual interior-point algorithms based on a new kernel function for linear optimization. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37 [7] Yu-Hong Dai, Xin-Wei Liu, Jie Sun. A primal-dual interior-point method capable of rapidly detecting infeasibility for nonlinear programs. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-27. doi: 10.3934/jimo.2018190 [8] Guoqiang Wang, Zhongchen Wu, Zhongtuan Zheng, Xinzhong Cai. Complexity analysis of primal-dual interior-point methods for semidefinite optimization based on a parametric kernel function with a trigonometric barrier term. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 101-113. doi: 10.3934/naco.2015.5.101 [9] Guowei Hua, Shouyang Wang, Chi Kin Chan, S. H. Hou. A fractional programming model for international facility location. Journal of Industrial & Management Optimization, 2009, 5 (3) : 629-649. doi: 10.3934/jimo.2009.5.629 [10] 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 & Management Optimization, 2017, 13 (5) : 1-34. doi: 10.3934/jimo.2019030 [11] Weihua Liu, Andrew Klapper. AFSRs synthesis with the extended Euclidean rational approximation algorithm. Advances in Mathematics of Communications, 2017, 11 (1) : 139-150. doi: 10.3934/amc.2017008 [12] Mostafa El Haffari, Ahmed Roubi. Prox-dual regularization algorithm for generalized fractional programs. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1991-2013. doi: 10.3934/jimo.2017028 [13] Shi Yan, Jun Liu, Haiyang Huang, Xue-Cheng Tai. A dual EM algorithm for TV regularized Gaussian mixture model in image segmentation. Inverse Problems & Imaging, 2019, 13 (3) : 653-677. doi: 10.3934/ipi.2019030 [14] Liping Zhang, Soon-Yi Wu. Robust solutions to Euclidean facility location problems with uncertain data. Journal of Industrial & Management Optimization, 2010, 6 (4) : 751-760. doi: 10.3934/jimo.2010.6.751 [15] Jean-Paul Arnaout, Georges Arnaout, John El Khoury. Simulation and optimization of ant colony optimization algorithm for the stochastic uncapacitated location-allocation problem. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1215-1225. doi: 10.3934/jimo.2016.12.1215 [16] David Julitz. Numerical approximation of atmospheric-ocean models with subdivision algorithm. Discrete & Continuous Dynamical Systems - A, 2007, 18 (2&3) : 429-447. doi: 10.3934/dcds.2007.18.429 [17] Zhenbo Wang. Worst-case performance of the successive approximation algorithm for four identical knapsacks. Journal of Industrial & Management Optimization, 2012, 8 (3) : 651-656. doi: 10.3934/jimo.2012.8.651 [18] Pierre Frankel. Alternating proximal algorithm with costs-to-move, dual description and application to PDE's. Discrete & Continuous Dynamical Systems - S, 2012, 5 (3) : 545-557. doi: 10.3934/dcdss.2012.5.545 [19] Meng Yu, Jack Xin. Stochastic approximation and a nonlocally weighted soft-constrained recursive algorithm for blind separation of reverberant speech mixtures. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1753-1767. doi: 10.3934/dcds.2010.28.1753 [20] Chenchen Wu, Dachuan Xu, Xin-Yuan Zhao. An improved approximation algorithm for the $2$-catalog segmentation problem using semidefinite programming relaxation. Journal of Industrial & Management Optimization, 2012, 8 (1) : 117-126. doi: 10.3934/jimo.2012.8.117

2018 Impact Factor: 1.025