Anapproximation algorithm for the $k$-level facility location problemwith submodular penalties

Gaidi Li; Zhen Wang; Dachuan Xu

doi:10.3934/jimo.2012.8.521

Article Contents

2012, Volume 8, Issue 3: 521-529. Doi: 10.3934/jimo.2012.8.521

This issue Previous Article Next Article Optimal investment with a value-at-risk constraint

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
2.
Department of Applied Mathematics, Beijing University of Technology, 100 Pingleyuan, Chaoyang District, Beijing, 100124

Received: April 2010

Revised: July 2011

Published: July 2012

Abstract Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 90C59; Secondary: 90C10.

Citation:

Related Papers

Cited by

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.