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

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

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 and 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-167. doi: 10.1016/S0020-0190(99)00144-1.
[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-217. doi: 10.1137/S0895480102417215.
[3]	A. F. Bumb and W. Kern, A simple dual ascent algorithm for the multilevel facility location problem, in "Approximation, Randomization, and Combinatorial Optimization" (Berkeley, CA, 2001), Lecture Notes in Comput. Sci., 2129, Springer, Berlin, (2001), 55-62.
[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-2231. doi: 10.1137/070708901.
[5]	M. Charikar, S. Khuller, D. M. Mount and G. Naraasimban, Algorithms for facility location problems with outliers, in "Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms" (Washington, DC, 2001), SIAM, Philadelphia, PA, (2001), 642-651.
[6]	X. Chen and B. Chen, Approximation algorithms for soft-capacitated facility location in capacitated network design, Algorithmica, 53 (2009), 263-297. doi: 10.1007/s00453-007-9032-7.
[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 "Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms," ACM, New York, (2007), 79-88.
[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-200. doi: 10.1007/s00453-011-9526-1.
[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-322. doi: 10.1016/S0166-218X(02)00458-4.
[10]	S. Guha and S. Khuller, Greedy strikes back: Improved facility location algorithms, in "Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms" (San Francisco, CA, 1998), ACM, New York, (1998), 649-657.
[11]	A. Hayrapetyan, C. Swamy and E. Tardos, Network design for information networks, in "Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms," ACM, New York, (2005), 933-942.
[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-824. doi: 10.1145/950620.950621.
[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-296. doi: 10.1145/375827.375845.
[14]	G. Li, Z. Wang and D. Xu, An approximation algorithm for the $k$-level facility location problem with submodular penalties, in "Global Optimization: Theory, Methods & Applications I, Lecture Notes in Decision Sciences'' (eds. C. Ma, L. Yu, D. Zhang and Z. Zhou), 12 (2009), 772-777.
[15]	S. Li, A 1.488-approximation algorithm for the uncapacitated facility location problem, in "Proceedings of Automata, Languages and Programming," Part II, Lecture Notes in Comput. Sci., 6756, Springer, Heidelberg, (2011), 77-88.
[16]	M. Mahdian, Y. Ye and J. Zhang, Approximation algorithms for metric facility location problems, SIAM Journal on Computing, 36 (2006), 411-432. doi: 10.1137/S0097539703435716.
[17]	J. Shu, An efficient greedy heuristic for warehouse-retailer network design optimization, Transportation Science, 44 (2010), 183-192. doi: 10.1287/trsc.1090.0302.
[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-241. doi: 10.1007/s10479-010-0732-z.
[19]	J. Shu, C.-P. Teo and Z.-J. Max Shen, Stochastic transportation-inventory network design problem, Operations Research, 53 (2005), 48-60. doi: 10.1287/opre.1040.0140.
[20]	D. B. Shmoys, E. Tardos and K. I. Aardal, Approximation algorithms for facility location problems (extended abstract), Proceedings of STOC, (1997), 265-274.
[21]	G. Xu and J. Xu, An LP rounding algorithm for approximating uncapacitated facility location problem with penalties, Information Processing Letters, 94 (2005), 119-123. doi: 10.1016/j.ipl.2005.01.005.
[22]	G. Xu and J. Xu, An improved approximation algorithm for uncapacitated facility location problem with penalties, Journal of Combinatorial Optimization, 17 (2009), 424-436. doi: 10.1007/s10878-007-9127-8.
[23]	J. Zhang, Approximating the two-level facility location problem via a quasi-greedy approach, Mathematical Programming, 108 (2006), 159-176. doi: 10.1007/s10107-006-0704-x.
[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-403. doi: 10.1287/moor.1040.0125.
[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-760.
[26]	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.

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-167. doi: 10.1016/S0020-0190(99)00144-1.
[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-217. doi: 10.1137/S0895480102417215.
[3]	A. F. Bumb and W. Kern, A simple dual ascent algorithm for the multilevel facility location problem, in "Approximation, Randomization, and Combinatorial Optimization" (Berkeley, CA, 2001), Lecture Notes in Comput. Sci., 2129, Springer, Berlin, (2001), 55-62.
[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-2231. doi: 10.1137/070708901.
[5]	M. Charikar, S. Khuller, D. M. Mount and G. Naraasimban, Algorithms for facility location problems with outliers, in "Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms" (Washington, DC, 2001), SIAM, Philadelphia, PA, (2001), 642-651.
[6]	X. Chen and B. Chen, Approximation algorithms for soft-capacitated facility location in capacitated network design, Algorithmica, 53 (2009), 263-297. doi: 10.1007/s00453-007-9032-7.
[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 "Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms," ACM, New York, (2007), 79-88.
[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-200. doi: 10.1007/s00453-011-9526-1.
[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-322. doi: 10.1016/S0166-218X(02)00458-4.
[10]	S. Guha and S. Khuller, Greedy strikes back: Improved facility location algorithms, in "Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms" (San Francisco, CA, 1998), ACM, New York, (1998), 649-657.
[11]	A. Hayrapetyan, C. Swamy and E. Tardos, Network design for information networks, in "Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms," ACM, New York, (2005), 933-942.
[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-824. doi: 10.1145/950620.950621.
[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-296. doi: 10.1145/375827.375845.
[14]	G. Li, Z. Wang and D. Xu, An approximation algorithm for the $k$-level facility location problem with submodular penalties, in "Global Optimization: Theory, Methods & Applications I, Lecture Notes in Decision Sciences'' (eds. C. Ma, L. Yu, D. Zhang and Z. Zhou), 12 (2009), 772-777.
[15]	S. Li, A 1.488-approximation algorithm for the uncapacitated facility location problem, in "Proceedings of Automata, Languages and Programming," Part II, Lecture Notes in Comput. Sci., 6756, Springer, Heidelberg, (2011), 77-88.
[16]	M. Mahdian, Y. Ye and J. Zhang, Approximation algorithms for metric facility location problems, SIAM Journal on Computing, 36 (2006), 411-432. doi: 10.1137/S0097539703435716.
[17]	J. Shu, An efficient greedy heuristic for warehouse-retailer network design optimization, Transportation Science, 44 (2010), 183-192. doi: 10.1287/trsc.1090.0302.
[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-241. doi: 10.1007/s10479-010-0732-z.
[19]	J. Shu, C.-P. Teo and Z.-J. Max Shen, Stochastic transportation-inventory network design problem, Operations Research, 53 (2005), 48-60. doi: 10.1287/opre.1040.0140.
[20]	D. B. Shmoys, E. Tardos and K. I. Aardal, Approximation algorithms for facility location problems (extended abstract), Proceedings of STOC, (1997), 265-274.
[21]	G. Xu and J. Xu, An LP rounding algorithm for approximating uncapacitated facility location problem with penalties, Information Processing Letters, 94 (2005), 119-123. doi: 10.1016/j.ipl.2005.01.005.
[22]	G. Xu and J. Xu, An improved approximation algorithm for uncapacitated facility location problem with penalties, Journal of Combinatorial Optimization, 17 (2009), 424-436. doi: 10.1007/s10878-007-9127-8.
[23]	J. Zhang, Approximating the two-level facility location problem via a quasi-greedy approach, Mathematical Programming, 108 (2006), 159-176. doi: 10.1007/s10107-006-0704-x.
[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-403. doi: 10.1287/moor.1040.0125.
[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-760.
[26]	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.

[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 and 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 and Optimization, 2011, 1 (3) : 509-528. doi: 10.3934/naco.2011.1.509
[3]	Kai Wang, Deren Han. On the linear convergence of the general first order primal-dual algorithm. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021134
[4]	Xiaojing Ye, Haomin Zhou. Fast total variation wavelet inpainting via approximated primal-dual hybrid gradient algorithm. Inverse Problems and Imaging, 2013, 7 (3) : 1031-1050. doi: 10.3934/ipi.2013.7.1031
[5]	Yu-Hong Dai, Zhouhong Wang, Fengmin Xu. A Primal-dual algorithm for unfolding neutron energy spectrum from multiple activation foils. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2367-2387. doi: 10.3934/jimo.2020073
[6]	Yishui Wang, Dongmei Zhang, Peng Zhang, Yong Zhang. Local search algorithm for the squared metric $ k $-facility location problem with linear penalties. Journal of Industrial and Management Optimization, 2021, 17 (4) : 2013-2030. doi: 10.3934/jimo.2020056
[7]	Jen-Yen Lin, Hui-Ju Chen, Ruey-Lin Sheu. Augmented Lagrange primal-dual approach for generalized fractional programming problems. Journal of Industrial and Management Optimization, 2013, 9 (4) : 723-741. doi: 10.3934/jimo.2013.9.723
[8]	Lican Kang, Yuan Luo, Jerry Zhijian Yang, Chang Zhu. A primal and dual active set algorithm for truncated $L_1$ regularized logistic regression. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022050
[9]	Lu Han, Min Li, Dachuan Xu, Dongmei Zhang. Stochastic-Lazier-Greedy Algorithm for monotone non-submodular maximization. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2607-2614. doi: 10.3934/jimo.2020085
[10]	Xin Sun, Dachuan Xu, Dongmei Zhang, Yang Zhou. An adaptive algorithm for maximization of non-submodular function with a matroid constraint. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022031
[11]	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 and Management Optimization, 2020, 16 (2) : 1009-1035. doi: 10.3934/jimo.2018190
[12]	Yanqin Bai, Xuerui Gao, Guoqiang Wang. Primal-dual interior-point algorithms for convex quadratic circular cone optimization. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 211-231. doi: 10.3934/naco.2015.5.211
[13]	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 and Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37
[14]	Yixuan Yang, Yuchao Tang, Meng Wen, Tieyong Zeng. Preconditioned Douglas-Rachford type primal-dual method for solving composite monotone inclusion problems with applications. Inverse Problems and Imaging, 2021, 15 (4) : 787-825. doi: 10.3934/ipi.2021014
[15]	Xiayang Zhang, Yuqian Kong, Shanshan Liu, Yuan Shen. A relaxed parameter condition for the primal-dual hybrid gradient method for saddle-point problem. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022008
[16]	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 and Optimization, 2015, 5 (2) : 101-113. doi: 10.3934/naco.2015.5.101
[17]	Ashkan Ayough, Farbod Farhadi, Mostafa Zandieh, Parisa Rastkhadiv. Genetic algorithm for obstacle location-allocation problems with customer priorities. Journal of Industrial and Management Optimization, 2021, 17 (4) : 1753-1769. doi: 10.3934/jimo.2020044
[18]	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
[19]	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
[20]	Nadia Hazzam, Zakia Kebbiche. A primal-dual interior point method for $ P_{\ast }\left( \kappa \right) $-HLCP based on a class of parametric kernel functions. Numerical Algebra, Control and Optimization, 2021, 11 (4) : 513-531. doi: 10.3934/naco.2020053

2020 Impact Factor: 1.801

Tools

Metrics

Other articles
by authors

on AIMS
Gaidi Li Zhen Wang Dachuan Xu
on Google Scholar
Gaidi Li Zhen Wang Dachuan Xu

[Back to Top]