-
Previous Article
Optimal investment with a value-at-risk constraint
- JIMO Home
- This Issue
- Next Article
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 |
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
[Back to Top]