Abstract
We present an improved approximation algorithm for k-level facility location problem with submodular penalties, the new approximation ratio is 2.9444 for any constant k, which improves the current best approximation ratio 3.314. The central ideas in our results are as follows: first, we restructure the problem as an uncapacitated facility location problem, then we use the primal-dual scheme with greedy augmentation. The key technique of our result is that we change the way of last opening facility set in primal-dual approximation algorithm to get much more tight result for k-level facility location problem with submodular penalties.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Data Availability
All data generated or analysed during this study are included in this published article [and its supplementary information files]
References
Byrka J, Rybicki B (2012) Improved LP-rounding approximation algorithm for \(k\)-level uncapacitated facility location. In: Automata, languages, and programming. Part I, Lecture Notes in Comput. Sci., vol 7391, Springer, Heidelberg, pp 157–169
Charikar M, Guha S (2005) Improved combinatorial algorithms for facility location problems. SIAM J Comput 34(4):803–824
Charikar M, Khuller S, Mount DM, Narasimhan G (2001) Algorithms for facility location problems with outliers (extended abstract). In: Proceedings of the twelfth annual ACM-SIAM symposium on discrete algorithms (Washington, DC, 2001), SIAM, Philadelphia, PA, pp 642–651
Chudak FA, Shmoys DB (2003) Improved approximation algorithms for the uncapacitated facility location problem. SIAM J Comput 33(1):1–25
Fujishige S (2005) Submodular functions and optimization. Ann Discrete Math, vol 58, 2nd edn. Elsevier B. V, Amsterdam
Hayrapetyan A, Swamy C, Tardos E (2005) Network design for information networks. In: Proceedings of the sixteenth annual ACM-SIAM symposium on discrete algorithms, ACM, New York, pp 933–942
Jain K, Vazirani VV (2001) Approximation algorithms for metric facility location and \(k\)-median problems using the primal-dual schema and Lagrangian relaxation. J ACM 48(2):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(6):795–824
Krishnaswamy R, Sviridenko M (2012) Inapproximability of the multi-level uncapacitated facility location problem. In: Proceedings of the twenty-third annual ACM-SIAM symposium on discrete algorithms, ACM, New York, pp 718–734
Li G, Wang Z, Xu D (2012) An approximation algorithm for the \(k\)-level facility location problem with submodular penalties. J Ind Manag Optim 8(3):521–529
Li G, Xu D, Du D, Wu C (2015) Approximation algorithms for the multilevel facility location problem with linear/submodular penalties. Front Algorithm. Springer International Publishing, Cham, pp 162–169
Li S (2013) A 1.488 approximation algorithm for the uncapacitated facility location problem. Inform Comput 222:45–58
Li Y, Du D, Xiu N, Xu D (2013) A combinatorial 2.375-approximation algorithm for the facility location problem with submodular penalties. Theoret Comput Sci 476:109–117
Li Y, Du D, Xiu N, Xu D (2015) Improved approximation algorithms for the facility location problems with linear/submodular penalties. Algorithmica 73(2):460–482
Mahdian M, Ye Y, Zhang J (2006) Approximation algorithms for metric facility location problems. SIAM J Comput 36(2):411–432
Qiu X, Kern W (2016) On the factor revealing lp approach for facility location with penalties. https://doi.org/10.48550/arXiv.1602.00192
Shmoys DB, Tardos E, Aardal K (1997) Approximation algorithms for facility location problems (extended abstract). In: Proceedings of the twenty-ninth annual ACM symposium on theory of computing, association for computing machinery, New York, NY, USA, STOC ’97, pp 265–274. https://doi.org/10.1145/258533.258600
Sviridenko M (2002) An improved approximation algorithm for the metric uncapacitated facility location problem. In: Integer programming and combinatorial optimization, Lecture Notes in Comput. Sci., vol 2337, Springer, Berlin, pp 240–257
Wang Y, Xu D, Du D, Wu C (2018) An approximation algorithm for \(k\)-facility location problem with linear penalties using local search scheme. J Comb Optim 36(1):264–279
Xu G, Xu J (2009) An improved approximation algorithm for uncapacitated facility location problem with penalties. J Comb Optim 17(4):424–436
Zhang P (2007) A new approximation algorithm for the \(k\)-facility location problem. Theoret Comput Sci 384(1):126–135
Zhang Z, Feng Q, Huang J, Wang J (2023) Improved approximation algorithms for solving the squared metric \(k\)-facility location problem. Theoret Comput Sci 942:107–122
Funding
The fund was provided by National Nature Science Foundation of China.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors have no relevant financial or non-financial interests to disclose.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
The research is supported by National Nature Science Foundation of China (No.12071126).
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Zhang, L., Yuan, J., Xu, Z. et al. A combinatorial approximation algorithm for k-level facility location problem with submodular penalties. J Comb Optim 46, 5 (2023). https://doi.org/10.1007/s10878-023-01067-w
Accepted:
Published:
DOI: https://doi.org/10.1007/s10878-023-01067-w