Abstract
We consider the k-level capacitated facility location problem (k-CFLP), which is a natural variant of the classical facility location problem and has applications in supply chain management. We obtain the first (combinatorial) approximation algorithm with a performance factor of \(k+2+\sqrt{k^{2}+2k+5}+\varepsilon\) (ε>0) for this problem.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Aardal KI, Chudak FA, Shmoys DB (1999) A 3-approximation algorithm for the k-level uncapacitated facility location problem. Inf Process Lett 72:161–167
Ageev A, Ye Y, Zhang J (2005) Improved combinatorial approximation algorithms for the k-level facility location problem. SIAM J Discrete Math 18:207–217
Byrka J, Aardal KI (2009) An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem, SIAM J Comput (to appear)
Chudak FA, Williamson DP (1999) Improved approximation algorithms for capacitied facility location problems. In: Proceedings of IPCO 1999, pp 99–113
Guha S, Kuller S (1999) Greedy strikes back: improved facility location algorithms. J Algorithms 31:228–248
Jain K, Vazirani VV (2001) Primal-dual approximation algorithms for metric facility location and k-median problems. J ACM 48:274–296
Jain K, Mahdian M, Markakis E, Saberi A, Vazirani VV (2003) Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. J ACM 50:795–824
Korupolu MR, Plaxton CG, Rajaraman R (1998) Analysis of a local search heuristic for facility location problems. In: Proceedings of SODA 1998, pp 1–10
Levi R, Shmoys DB, Swamy C (2004) LP-based approximation algorithms for capacitated facility location (extended abstract). In: Proceedings of IPCO 2004, pp 206–218
Mahdian M, Pal M (2003) Universal facility location. In: Proceedings of ESA 2003, pp 409–421
Mahdian M, Ye Y, Zhang J (2006) Approximation algorithms for metric facility location problems. SIAM J Comput 36:411–432
Pal M, Tardos E, Wexler T (2001) Facility location with hard capacities. In: Proceedings of FOCS 2001, pp 329–338
Shmoys DB, Tardos E, Aardal KI (1997) Approximation algorithms for facility location problems. In: Proceedings of STOC 1997, pp 265–274
Xu D, Du D (2006) The k-level facility location game. Oper Res Lett 34:421–426
Xu D, Zhang S (2008) Approximation algorithm for facility location with service installation costs. Oper Res Lett 36:46–50
Zhang J (2006) Approximating the two-level facility location problem via a quasi-greedy approach. Math Program 108:159–176
Zhang J, Chen B, Ye Y (2005) A multiexchange local search algorithm for the capacitated facility location problem. Math Oper Res 30:389–403
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Du, D., Wang, X. & Xu, D. An approximation algorithm for the k-level capacitated facility location problem. J Comb Optim 20, 361–368 (2010). https://doi.org/10.1007/s10878-009-9213-1
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-009-9213-1