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

Previous Article
JIMO Home
This Issue
Next Article
Optimal investment with a value-at-risk constraint

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

Gaidi Li ^1, , Zhen Wang ^1, and Dachuan Xu ^2,

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

Abstract
Related Papers

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.

Keywords: submodular., approximation algorithm, primal-dual, Facility location, combinatorial algorithm.

Mathematics Subject Classification: Primary: 90C59; Secondary: 90C1.

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

American Institute of Mathematical Sciences