American Institute of Mathematical Sciences

Advanced
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

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-167. 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-217. 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 "Approximation, Randomization, and Combinatorial Optimization" (Berkeley, CA, 2001), Lecture Notes in Comput. Sci., 2129, Springer, Berlin, (2001), 55-62.  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-2231. 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 "Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms" (Washington, DC, 2001), SIAM, Philadelphia, PA, (2001), 642-651.  Google Scholar

[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.  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 "Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms," ACM, New York, (2007), 79-88.  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-200. 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-322. doi: 10.1016/S0166-218X(02)00458-4.  Google Scholar

[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.  Google Scholar

[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.  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-824. 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-296. 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 "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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  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-241. 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-60. 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-274. 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-123. 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-436. 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-176. 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-403. 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-760.  Google Scholar

[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.  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-167. 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-217. 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 "Approximation, Randomization, and Combinatorial Optimization" (Berkeley, CA, 2001), Lecture Notes in Comput. Sci., 2129, Springer, Berlin, (2001), 55-62.  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-2231. 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 "Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms" (Washington, DC, 2001), SIAM, Philadelphia, PA, (2001), 642-651.  Google Scholar

[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.  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 "Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms," ACM, New York, (2007), 79-88.  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-200. 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-322. doi: 10.1016/S0166-218X(02)00458-4.  Google Scholar

[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.  Google Scholar

[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.  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-824. 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-296. 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 "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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  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-241. 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-60. 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-274. 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-123. 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-436. 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-176. 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-403. 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-760.  Google Scholar

[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.  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]

Kai Wang, Deren Han. On the linear convergence of the general first order primal-dual algorithm. Journal of Industrial & 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 & 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 & 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 & 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 & Management Optimization, 2013, 9 (4) : 723-741. doi: 10.3934/jimo.2013.9.723
[8]

Lu Han, Min Li, Dachuan Xu, Dongmei Zhang. Stochastic-Lazier-Greedy Algorithm for monotone non-submodular maximization. Journal of Industrial & Management Optimization, 2021, 17 (5) : 2607-2614. doi: 10.3934/jimo.2020085
[9]

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, 2020, 16 (2) : 1009-1035. doi: 10.3934/jimo.2018190
[10]

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
[11]

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
[12]

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 & Imaging, 2021, 15 (4) : 787-825. doi: 10.3934/ipi.2021014
[13]

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
[14]

Ashkan Ayough, Farbod Farhadi, Mostafa Zandieh, Parisa Rastkhadiv. Genetic algorithm for obstacle location-allocation problems with customer priorities. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1753-1769. doi: 10.3934/jimo.2020044
[15]

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, 2020, 16 (4) : 1801-1834. doi: 10.3934/jimo.2019030
[16]

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
[17]

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
[18]

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 & Optimization, 2021, 11 (4) : 513-531. doi: 10.3934/naco.2020053
[19]

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
[20]

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

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (41)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences