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

Wolfgang Riedl, Robert Baier, Matthias Gerdts. Optimization-based subdivision algorithm for reachable sets. Journal of Computational Dynamics, 2021, 8 (1) : 99-130. doi: 10.3934/jcd.2021005
[2]

Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017
[3]

Cheng Peng, Zhaohui Tang, Weihua Gui, Qing Chen, Jing He. A bidirectional weighted boundary distance algorithm for time series similarity computation based on optimized sliding window size. Journal of Industrial & Management Optimization, 2021, 17 (1) : 205-220. doi: 10.3934/jimo.2019107
[4]

Shun Zhang, Jianlin Jiang, Su Zhang, Yibing Lv, Yuzhen Guo. ADMM-type methods for generalized multi-facility Weber problem. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020171
[5]

Yifan Chen, Thomas Y. Hou. Function approximation via the subsampled Poincaré inequality. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 169-199. doi: 10.3934/dcds.2020296
[6]

Mostafa Mbekhta. Representation and approximation of the polar factor of an operator on a Hilbert space. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020463
[7]

Zonghong Cao, Jie Min. Selection and impact of decision mode of encroachment and retail service in a dual-channel supply chain. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020167
[8]

Manuel Friedrich, Martin Kružík, Jan Valdman. Numerical approximation of von Kármán viscoelastic plates. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 299-319. doi: 10.3934/dcdss.2020322
[9]

Pierluigi Colli, Gianni Gilardi, Jürgen Sprekels. Deep quench approximation and optimal control of general Cahn–Hilliard systems with fractional operators and double obstacle potentials. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 243-271. doi: 10.3934/dcdss.2020213

2019 Impact Factor: 1.366

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences