{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,18]],"date-time":"2025-12-18T14:25:34Z","timestamp":1766067934488,"version":"3.37.3"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,2,26]],"date-time":"2024-02-26T00:00:00Z","timestamp":1708905600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,2,26]],"date-time":"2024-02-26T00:00:00Z","timestamp":1708905600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["12071126"],"award-info":[{"award-number":["12071126"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2024,3]]},"DOI":"10.1007\/s10878-024-01106-0","type":"journal-article","created":{"date-parts":[[2024,2,26]],"date-time":"2024-02-26T12:02:45Z","timestamp":1708948965000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Approximation algorithms for the fault-tolerant facility location problem with submodular penalties"],"prefix":"10.1007","volume":"47","author":[{"given":"Yingying","family":"Guo","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5428-4414","authenticated-orcid":false,"given":"Qiaoliang","family":"Li","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,2,26]]},"reference":[{"issue":"1","key":"1106_CR1","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1137\/151002320","volume":"46","author":"H An","year":"2017","unstructured":"An H, Singh M, Svensson O (2017) LP-based algorithms for capacitated facility location. SIAM J Comput 46(1):272\u2013306","journal-title":"SIAM J Comput"},{"issue":"6","key":"1106_CR2","doi-asserted-by":"publisher","first-page":"2212","DOI":"10.1137\/070708901","volume":"39","author":"J Byrka","year":"2010","unstructured":"Byrka J, Aardal K (2010) An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem. SIAM J Comput 39(6):2212\u20132231","journal-title":"SIAM J Comput"},{"key":"1106_CR3","doi-asserted-by":"crossref","unstructured":"Byrka J, Srinivasan A, Swamy C (2010) Fault-tolerant facility location: a randomized dependent LP-rounding algorithm. In: Integer programming and combinatorial optimization, 14th International Conference, Lecture Notes in Computer Science, vol 6080. Springer, pp 244\u2013257","DOI":"10.1007\/978-3-642-13036-6_19"},{"issue":"2","key":"1106_CR4","doi-asserted-by":"publisher","first-page":"991","DOI":"10.1007\/s10107-022-01799-3","volume":"197","author":"D Chakrabarty","year":"2023","unstructured":"Chakrabarty D, Negahbani M (2023) Robust k-center with two types of radii. Math Program 197(2):991\u20131007","journal-title":"Math Program"},{"key":"1106_CR5","doi-asserted-by":"crossref","unstructured":"Charikar M, Guha S (1999) Improved combinatorial algorithms for the facility location and k-median problems. In: 40th Annual symposium on foundations of computer science. IEEE Computer Society, pp 378\u2013388","DOI":"10.1109\/SFFCS.1999.814609"},{"key":"1106_CR6","unstructured":"Chudak FA, Nagano K (2007) Efficient solutions to relaxations of combinatorial problems with submodular penalties via the Lov\u00e1sz extension and non-smooth convex optimization. In: Proceedings of the eighteenth annual ACM-SIAM symposium on discrete algorithms. SIAM, pp 79\u201388"},{"issue":"1","key":"1106_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0097539703405754","volume":"33","author":"FA Chudak","year":"2003","unstructured":"Chudak FA, Shmoys DB (2003) Improved approximation algorithms for the uncapacitated facility location problem. SIAM J Comput 33(1):1\u201325","journal-title":"SIAM J Comput"},{"key":"1106_CR8","doi-asserted-by":"crossref","unstructured":"Cohen-Addad V, Grandoni F, Lee E, Schwiegelshohn C (2023) Breaching the 2 LMP approximation barrier for facility location with applications to k-median. In: Proceedings of the 2023 ACM-SIAM symposium on discrete algorithms, SODA. SIAM, pp 940\u2013986","DOI":"10.1137\/1.9781611977554.ch37"},{"issue":"1\u20132","key":"1106_CR9","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/s00453-011-9526-1","volume":"63","author":"D Du","year":"2012","unstructured":"Du D, Lu R, Xu D (2012) A primal-dual approximation algorithm for the facility location problem with submodular penalties. Algorithmica 63(1\u20132):191\u2013200","journal-title":"Algorithmica"},{"key":"1106_CR10","unstructured":"Fujishige S (2005) Submodular functions and optimization. In: Annals of Discrete Mathematics, vol 58, 2nd edn. Elsevier, Amsterdam"},{"issue":"2","key":"1106_CR11","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1016\/S0196-6774(03)00056-7","volume":"48","author":"S Guha","year":"2003","unstructured":"Guha S, Meyerson A, Munagala K (2003) A constant factor approximation algorithm for the fault-tolerant facility location problem. J Algorithms 48(2):429\u2013440","journal-title":"J Algorithms"},{"key":"1106_CR12","unstructured":"Hayrapetyan A, Swamy C, Tardos \u00c9 (2005) Network design for information networks. In: Proceedings of the sixteenth annual ACM-SIAM symposium on discrete algorithms, SODA. pp 933\u2013942"},{"issue":"2","key":"1106_CR13","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1145\/375827.375845","volume":"48","author":"K Jain","year":"2001","unstructured":"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\u2013296","journal-title":"J ACM"},{"issue":"3","key":"1106_CR14","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/s00453-003-1070-1","volume":"38","author":"K Jain","year":"2004","unstructured":"Jain K, Vazirani VV (2004) An approximation algorithm for the fault tolerant metric facility location problem. Algorithmica 38(3):433\u2013439","journal-title":"Algorithmica"},{"issue":"6","key":"1106_CR15","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1145\/950620.950621","volume":"50","author":"K Jain","year":"2003","unstructured":"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\u2013824","journal-title":"J ACM"},{"key":"1106_CR16","unstructured":"Kamiyama N (2013) The fault-tolerant facility location problem with submodular penalties. In: MI preprint series, pp 1\u201315"},{"key":"1106_CR17","unstructured":"Korupolu MR, Plaxton CG, Rajaraman R (1998) Analysis of a local search heuristic for facility location problems. In: Proceedings of the ninth annual ACM-SIAM symposium on discrete algorithms. ACM\/SIAM, pp 1\u201310"},{"key":"1106_CR18","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/j.ic.2012.01.007","volume":"222","author":"S Li","year":"2013","unstructured":"Li S (2013) A 1.488 approximation algorithm for the uncapacitated facility location problem. Inf Comput 222:45\u201358","journal-title":"Inf Comput"},{"issue":"2","key":"1106_CR19","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1007\/s00453-014-9911-7","volume":"73","author":"Y Li","year":"2015","unstructured":"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\u2013482","journal-title":"Algorithmica"},{"issue":"5","key":"1106_CR20","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/0020-0190(92)90208-D","volume":"44","author":"J Lin","year":"1992","unstructured":"Lin J, Vitter JS (1992) Approximation algorithms for geometric median problems. Inf Process Lett 44(5):245\u2013249","journal-title":"Inf Process Lett"},{"issue":"2","key":"1106_CR21","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1137\/S0097539703435716","volume":"36","author":"M Mahdian","year":"2006","unstructured":"Mahdian M, Ye Y, Zhang J (2006) Approximation algorithms for metric facility location problems. SIAM J Comput 36(2):411\u2013432","journal-title":"SIAM J Comput"},{"key":"1106_CR22","doi-asserted-by":"crossref","unstructured":"Shmoys DB, Tardos \u00c9, Aardal K (1997) Approximation algorithms for facility location problems (extended abstract). In: Proceedings of the twenty-ninth annual ACM symposium on the theory of computing. ACM, pp 265\u2013274","DOI":"10.1145\/258533.258600"},{"key":"1106_CR23","doi-asserted-by":"crossref","unstructured":"Sviridenko M (2002) An improved approximation algorithm for the metric uncapacitated facility location problem. In: Integer programming and combinatorial optimization, 9th International IPCO conference. Springer, pp 240\u2013257","DOI":"10.1007\/3-540-47867-1_18"},{"issue":"4","key":"1106_CR24","doi-asserted-by":"publisher","first-page":"51:1","DOI":"10.1145\/1383369.1383382","volume":"4","author":"C Swamy","year":"2008","unstructured":"Swamy C, Shmoys DB (2008) Fault-tolerant facility location. ACM Trans Algorithms 4(4):51:1-51:27","journal-title":"ACM Trans Algorithms"},{"key":"1106_CR25","volume-title":"The design of approximation algorithms","author":"DP Williamson","year":"2010","unstructured":"Williamson DP, Shmoys DB (2010) The design of approximation algorithms. Cambridge University Press, Cambridge"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01106-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-024-01106-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01106-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T23:14:26Z","timestamp":1710285266000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-024-01106-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,26]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,3]]}},"alternative-id":["1106"],"URL":"https:\/\/doi.org\/10.1007\/s10878-024-01106-0","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2024,2,26]]},"assertion":[{"value":"10 January 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 February 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"14"}}