{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T22:38:10Z","timestamp":1775083090501,"version":"3.50.1"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,8,1]],"date-time":"2020-08-01T00:00:00Z","timestamp":1596240000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,8,1]],"date-time":"2020-08-01T00:00:00Z","timestamp":1596240000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"Natural Science Foundation of China","doi-asserted-by":"crossref","award":["11531014"],"award-info":[{"award-number":["11531014"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"Natural Science Foundation of China","doi-asserted-by":"crossref","award":["11871081"],"award-info":[{"award-number":["11871081"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"Natural Science Foundation of China","doi-asserted-by":"crossref","award":["11901558"],"award-info":[{"award-number":["11901558"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"China Postdoctoral Science Foundation funded project","award":["2018M643233"],"award-info":[{"award-number":["2018M643233"]}]},{"DOI":"10.13039\/501100001809","name":"Natural Science Foundation of China","doi-asserted-by":"crossref","award":["11871081"],"award-info":[{"award-number":["11871081"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2020,10]]},"DOI":"10.1007\/s10878-020-00631-y","type":"journal-article","created":{"date-parts":[[2020,8,1]],"date-time":"2020-08-01T13:02:42Z","timestamp":1596286962000},"page":"848-860","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Approximating the $$\\tau $$-relaxed soft capacitated facility location problem"],"prefix":"10.1007","volume":"40","author":[{"given":"Lu","family":"Han","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dachuan","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yicheng","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7933-0034","authenticated-orcid":false,"given":"Dongmei","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,8,1]]},"reference":[{"key":"631_CR1","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/S0020-0190(99)00144-1","volume":"72","author":"KI Aardal","year":"1999","unstructured":"Aardal KI, Chudak FA, Shmoys DB (1999) A $$3$$-approximation algorithm for the $$k$$-level uncapacitated facility location problem. Inf Process Lett 72:161\u2013167","journal-title":"Inf Process Lett"},{"key":"631_CR2","doi-asserted-by":"publisher","DOI":"10.1137\/18M1171321","author":"S Ahmadian","year":"2019","unstructured":"Ahmadian S, Norouzi-Fard A, Svensson O, Ward J (2019) Better guarantees for $$k$$-means and Euclidean $$k$$-median by primal-dual algorithms. SIAM J Comput. https:\/\/doi.org\/10.1137\/18M1171321","journal-title":"SIAM J Comput"},{"key":"631_CR3","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1137\/S0097539702416402","volume":"33","author":"V Arya","year":"2004","unstructured":"Arya V, Garg N, Khandekar R, Meyerson A, Munagala K, Pandit V (2004) Local search heuristics for $$k$$-median and facility location problems. SIAM J Comput 33:544\u2013562","journal-title":"SIAM J Comput"},{"key":"631_CR4","doi-asserted-by":"publisher","first-page":"2212","DOI":"10.1137\/070708901","volume":"39","author":"J Byrka","year":"2010","unstructured":"Byrka J, Aardal KI (2010) An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem. SIAM J Comput 39:2212\u20132231","journal-title":"SIAM J Comput"},{"key":"631_CR5","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/s00224-014-9575-3","volume":"58","author":"J Byrka","year":"2016","unstructured":"Byrka J, Li S, Rybicki B (2016) Improved approximation algorithm for $$k$$-level uncapacitated facility location problem (with penalties). Theory Comput Syst 58:19\u201344","journal-title":"Theory Comput Syst"},{"key":"631_CR6","doi-asserted-by":"crossref","unstructured":"Byrka J, Pensyl T, Rybicki B, Srinivasan A, Trinh K (2017) An improved approximation for $$k$$-median, and positive correlation in budgeted optimization. ACM Trans Algorithms 13(2):23:1\u201323:31","DOI":"10.1145\/2981561"},{"key":"631_CR7","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1006\/jcss.2002.1882","volume":"65","author":"M Charikar","year":"2002","unstructured":"Charikar M, Guha S, Tardos \u00c9, Shmoys DB (2002) A constant-factor approximation algorithm for the $$k$$-median problem. J Comput Syst Sci 65:129\u2013149","journal-title":"J Comput Syst Sci"},{"key":"631_CR8","unstructured":"Charikar M, Khuller S, Mount DM, Narasimhan G (2001) Algorithms for facility location problems with outliers. In: Proceedings of SODA, pp 642\u2013651"},{"key":"631_CR9","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\u201325","journal-title":"SIAM J Comput"},{"key":"631_CR10","doi-asserted-by":"publisher","first-page":"655","DOI":"10.1007\/s10107-014-0821-x","volume":"153","author":"CG Fernandes","year":"2015","unstructured":"Fernandes CG, Meira LAA, Miyazawa FK, Pedrosa LLC (2015) A systematic approach to bound factor-revealing LPs and its application to the metric and squared metric facility location problems. Math Program 153:655\u2013685","journal-title":"Math Program"},{"key":"631_CR11","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1006\/jagm.1998.0993","volume":"31","author":"S Guha","year":"1999","unstructured":"Guha S, Khuller S (1999) Greedy strikes back: Improved facility location algorithms. J Algorithms 31:228\u2013248","journal-title":"J Algorithms"},{"key":"631_CR12","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1007\/BF01581035","volume":"22","author":"DS Hochbaum","year":"1982","unstructured":"Hochbaum DS (1982) Heuristics for the fixed cost median problem. Math program 22:148\u2013162","journal-title":"Math program"},{"key":"631_CR13","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 E, Vazirani VV (2003) Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. J ACM 50:795\u2013824","journal-title":"J ACM"},{"key":"631_CR14","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:274\u2013296","journal-title":"J ACM"},{"key":"631_CR15","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1287\/mnsc.9.4.643","volume":"9","author":"AA Kuehn","year":"1963","unstructured":"Kuehn AA, Hamburger MJ (1963) A heuristic program for locating warehouses. Manag Sci 9:643\u2013666","journal-title":"Manag Sci"},{"key":"631_CR16","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"},{"key":"631_CR17","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:460\u2013482","journal-title":"Algorithmica"},{"key":"631_CR18","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/0020-0190(92)90208-D","volume":"44","author":"JH Lin","year":"1992","unstructured":"Lin JH, Vitter JS (1992) Approximation algorithms for geometric median problems. Inf Process Lett 44:245\u2013249","journal-title":"Inf Process Lett"},{"key":"631_CR19","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:411\u2013432","journal-title":"SIAM J Comput"},{"key":"631_CR20","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1287\/mnsc.11.2.213","volume":"11","author":"AS Manne","year":"1964","unstructured":"Manne AS (1964) Plant location under economies-of-scale-decentralization and computation. Manag Sci 11:213\u2013235","journal-title":"Manag Sci"},{"key":"631_CR21","doi-asserted-by":"crossref","unstructured":"Pal M, Tardos \u00c9, Wexler T (2001) Facility location with nonuniform hard capacities. In: Proceedings of FOCS, pp 329\u2013338","DOI":"10.1109\/SFCS.2001.959907"},{"key":"631_CR22","doi-asserted-by":"crossref","unstructured":"Shmoys DB, Tardos \u00c9, Aardal KI (1997) Approximation algorithms for facility location problems. In: Proceedings of STOC, pp 265\u2013274","DOI":"10.1145\/258533.258600"},{"key":"631_CR23","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1287\/opre.1040.0140","volume":"53","author":"J Shu","year":"2005","unstructured":"Shu J, Teo CP, Shen ZJM (2005) Stochastic transportation-inventory network design problem. Oper Res 53:48\u201360","journal-title":"Oper Res"},{"key":"631_CR24","doi-asserted-by":"publisher","first-page":"631","DOI":"10.2307\/1235442","volume":"45","author":"JF Stollsteimer","year":"1963","unstructured":"Stollsteimer JF (1963) A working model for plant numbers and locations. J Farm Econ 45:631\u2013645","journal-title":"J Farm Econ"},{"key":"631_CR25","doi-asserted-by":"crossref","unstructured":"Sviridenko M (2002) An improved approximation algorithm for the metric uncapacitated facility location problem. In: Proceedings of IPCO, pp 240\u2013257","DOI":"10.1007\/3-540-47867-1_18"},{"key":"631_CR26","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1287\/opre.1030.0096","volume":"52","author":"CP Teo","year":"2004","unstructured":"Teo CP, Shu J (2004) Warehouse-retailer network design problem. Oper Res 52:396\u2013408","journal-title":"Oper Res"},{"key":"631_CR27","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1007\/s40305-013-0034-7","volume":"1","author":"C Wu","year":"2013","unstructured":"Wu C, Xu D, Shu J (2013) An approximation algorithm for the stochastic fault-tolerant facility location problem. J Oper Res Soc China 1:511\u2013522","journal-title":"J Oper Res Soc China"},{"key":"631_CR28","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2020.05.038","author":"Y Xu","year":"2020","unstructured":"Xu Y, Xu D, Zhang Y, Zou J (2020) M$$^p$$UFLP: universal facility location problem in the $$p$$-th power of metric space. Theor Comput Sci. https:\/\/doi.org\/10.1016\/j.tcs.2020.05.038","journal-title":"Theor Comput Sci"},{"key":"631_CR29","unstructured":"Young NE (2000) $$k$$-medians, facility location, and the Chernoff-Wald bound. In: Proceedings of SODA, pp 86\u201395"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00631-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-020-00631-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00631-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,31]],"date-time":"2021-07-31T23:46:48Z","timestamp":1627775208000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-020-00631-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,1]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,10]]}},"alternative-id":["631"],"URL":"https:\/\/doi.org\/10.1007\/s10878-020-00631-y","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,1]]},"assertion":[{"value":"1 August 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}