-
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.
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.
doi: 10.1137/S0895480102417215. |
[3] |
A. F. Bumb and W. Kern, A simple dual ascent algorithm for the multilevel facility location problem,, in, 2129 (2001), 55.
|
[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. |
[5] |
M. Charikar, S. Khuller, D. M. Mount and G. Naraasimban, Algorithms for facility location problems with outliers,, in, (2001), 642.
|
[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. |
[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.
|
[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. |
[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. |
[10] |
S. Guha and S. Khuller, Greedy strikes back: Improved facility location algorithms,, in, (1998), 649.
|
[11] |
A. Hayrapetyan, C. Swamy and E. Tardos, Network design for information networks,, in, (2005), 933.
|
[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. |
[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. |
[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.
|
[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. |
[17] |
J. Shu, An efficient greedy heuristic for warehouse-retailer network design optimization,, Transportation Science, 44 (2010), 183.
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.
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.
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. 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. |
[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. |
[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. |
[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. |
[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.
|
[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. |
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. |
[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. |
[3] |
A. F. Bumb and W. Kern, A simple dual ascent algorithm for the multilevel facility location problem,, in, 2129 (2001), 55.
|
[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. |
[5] |
M. Charikar, S. Khuller, D. M. Mount and G. Naraasimban, Algorithms for facility location problems with outliers,, in, (2001), 642.
|
[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. |
[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.
|
[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. |
[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. |
[10] |
S. Guha and S. Khuller, Greedy strikes back: Improved facility location algorithms,, in, (1998), 649.
|
[11] |
A. Hayrapetyan, C. Swamy and E. Tardos, Network design for information networks,, in, (2005), 933.
|
[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. |
[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. |
[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.
|
[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. |
[17] |
J. Shu, An efficient greedy heuristic for warehouse-retailer network design optimization,, Transportation Science, 44 (2010), 183.
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.
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.
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. 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. |
[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. |
[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. |
[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. |
[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.
|
[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. |
[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] |
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 |
[10] |
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 |
[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] |
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 |
[15] |
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 |
[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
Tools
Metrics
Other articles
by authors
[Back to Top]