{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T09:29:32Z","timestamp":1758274172301,"version":"3.37.3"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,2,11]],"date-time":"2020-02-11T00:00:00Z","timestamp":1581379200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,2,11]],"date-time":"2020-02-11T00:00:00Z","timestamp":1581379200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100010882","name":"Tianjin Municipal Education Commission","doi-asserted-by":"publisher","award":["2018KJ149"],"award-info":[{"award-number":["2018KJ149"]}],"id":[{"id":"10.13039\/501100010882","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["283106"],"award-info":[{"award-number":["283106"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11771386","11728104"],"award-info":[{"award-number":["11771386","11728104"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National 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":[[2022,10]]},"DOI":"10.1007\/s10878-020-00538-8","type":"journal-article","created":{"date-parts":[[2020,2,11]],"date-time":"2020-02-11T17:04:42Z","timestamp":1581440682000},"page":"1680-1692","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["An approximation algorithm for stochastic multi-level facility location problem with soft capacities"],"prefix":"10.1007","volume":"44","author":[{"given":"Chenchen","family":"Wu","sequence":"first","affiliation":[]},{"given":"Donglei","family":"Du","sequence":"additional","affiliation":[]},{"given":"Yue","family":"Kang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,2,11]]},"reference":[{"doi-asserted-by":"publisher","unstructured":"Afrashteh E, Alizadeh B, Baroughi F (2018) Optimal algorithms for integer inverse undesirable $$p$$-median location problems on weighted extended star networks. J Oper Res Soc China. https:\/\/doi.org\/10.1007\/s40305-018-0229-z","key":"538_CR1","DOI":"10.1007\/s40305-018-0229-z"},{"key":"538_CR2","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 problem. SIAM J Comput 33:544\u2013562","journal-title":"SIAM J Comput"},{"key":"538_CR3","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1137\/151002320","volume":"46","author":"HC An","year":"2017","unstructured":"An HC, Singh M, Svensson O (2017) LP-based algorithms for capacitated facility location. SIAM J Comput 46:272\u2013306","journal-title":"SIAM J Comput"},{"key":"538_CR4","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1137\/S0895480102417215","volume":"18","author":"AA Ageev","year":"2004","unstructured":"Ageev AA, Ye Y, Zhang J (2004) Improved combinatorial approximation algorithms for the $$k$$-level facility location problem. SIAM J Discret Math 18:207\u2013217","journal-title":"SIAM J Discret Math"},{"key":"538_CR5","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:2212\u20132231","journal-title":"SIAM J Comput"},{"doi-asserted-by":"crossref","unstructured":"Bumb AF, Kern, W (2001) A simple dual ascent algorithm for the multilevel facility location problem. In: Proceedings of APPROX, pp 55-63","key":"538_CR6","DOI":"10.1007\/3-540-44666-4_10"},{"issue":"23","key":"538_CR7","first-page":"737","volume":"13","author":"J Bryka","year":"2017","unstructured":"Bryka 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(23):737\u2013756","journal-title":"ACM Trans Algorithms"},{"key":"538_CR8","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":"538_CR9","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1016\/j.dam.2009.11.007","volume":"158","author":"A Gabor","year":"2010","unstructured":"Gabor A, van Ommeren J (2010) A new approximation algorithm for the multilevel facility location problem. Discret Appl Math 158:453\u2013460","journal-title":"Discret Appl Math"},{"key":"538_CR10","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:795\u2013824","journal-title":"J ACM"},{"key":"538_CR11","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":"538_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2907050","volume":"13","author":"R Krishnaswamy","year":"2016","unstructured":"Krishnaswamy R, Sviridenko M (2016) Inapproximability of the multilevel uncapacitated facility location problem. ACM Trans Algorithms 13:1\u201325","journal-title":"ACM Trans Algorithms"},{"doi-asserted-by":"crossref","unstructured":"Li S (2011) A 1.488 -approximation algorithm for the uncapacitated facility location problem. In: Proceedings of ICALP, Part II, pp 77\u201388","key":"538_CR13","DOI":"10.1007\/978-3-642-22012-8_5"},{"doi-asserted-by":"crossref","unstructured":"Li S (2019) On Facility Location with General Lower Bounds. In Proceedings of SODA, pp 2279\u20132290","key":"538_CR14","DOI":"10.1137\/1.9781611975482.138"},{"key":"538_CR15","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1137\/130938645","volume":"45","author":"S Li","year":"2016","unstructured":"Li S, Svensson O (2016) Approximating $$k$$-median via pseudo-approximation. SIAM J Comput 45:530\u2013547","journal-title":"SIAM J Comput"},{"key":"538_CR16","doi-asserted-by":"publisher","first-page":"1950006","DOI":"10.1142\/S0217595919500064","volume":"36","author":"M Li","year":"2019","unstructured":"Li M, Xu D, Zhang D, Zhang T (2019) A streaming algorithm for k-means with approximate coreset. Asia-Pac J Oper Res 36:1950006","journal-title":"Asia-Pac J Oper Res"},{"key":"538_CR17","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1007\/s10878-017-0179-0","volume":"35","author":"L Han","year":"2018","unstructured":"Han L, Xu D, Du D, Zhang D (2018) A local search approximation algorithm for the uniform capacitated k-facility location problem. J Comb Optim 35:409\u2013423","journal-title":"J Comb Optim"},{"doi-asserted-by":"crossref","unstructured":"Mahdian M, Ye Y, Zhang J (2003) A 2-approximation algorithm for the soft-capacitated facility location problem. In: Proceedings of APPROX, pp 149\u2013162","key":"538_CR18","DOI":"10.1007\/978-3-540-45198-3_12"},{"key":"538_CR19","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/s10107-005-0673-5","volume":"108","author":"R Ravi","year":"2006","unstructured":"Ravi R, Sinha A (2006) Hedging uncertainty: approximation algorithhms for stochastic optimization problems. Math Program 108:97\u2013114","journal-title":"Math Program"},{"unstructured":"Srinivasan A (2007) Approximation algorithms for stochastic and risk-averse optimization. In: Proceedings of SODA. pp 1305\u20131313","key":"538_CR20"},{"key":"538_CR21","doi-asserted-by":"publisher","first-page":"978","DOI":"10.1145\/1217856.1217860","volume":"53","author":"DB Shmoys","year":"2006","unstructured":"Shmoys DB, Swamy C (2006) An approximation scheme for stochastic linear programming and its application to stochastic integer programs. J ACM 53:978\u20131012","journal-title":"J ACM"},{"doi-asserted-by":"crossref","unstructured":"Shmoys DB, Tard\u00f6s E, Aardal KI (1997) Approximation algorithms for facility location problems. In: Proceedings of STOC, pp 265\u2013274","key":"538_CR22","DOI":"10.1145\/258533.258600"},{"unstructured":"Sviridenko M (1998) Cited as personal communication in [8]","key":"538_CR23"},{"key":"538_CR24","doi-asserted-by":"publisher","first-page":"1015","DOI":"10.1007\/s10255-017-0714-x","volume":"33","author":"W Wu","year":"2017","unstructured":"Wu W, Xu D (2017) An improved approximation algorithm for the $$k$$-level facility location problem with soft capacities. Acta Mathematicae Applicatae Sinica, English Series 33:1015\u20131024","journal-title":"Acta Mathematicae Applicatae Sinica, English Series"},{"doi-asserted-by":"crossref","unstructured":"Ye, Y., Zhang, J (2005) An approximation algorithm for the dynamic facility location problem. In: Combinatorial optimization in communication networks. Kluwer Academic Publishers, pp 623\u2013637","key":"538_CR25","DOI":"10.1007\/0-387-29026-5_22"},{"key":"538_CR26","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/s10107-006-0704-x","volume":"108","author":"J Zhang","year":"2006","unstructured":"Zhang J (2006) Approximating the two-level facility location problem via a quasi-greedy approach. Math Program 108:159\u2013176","journal-title":"Math Program"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00538-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-020-00538-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00538-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,28]],"date-time":"2022-09-28T08:43:52Z","timestamp":1664354632000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-020-00538-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,11]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["538"],"URL":"https:\/\/doi.org\/10.1007\/s10878-020-00538-8","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2020,2,11]]},"assertion":[{"value":"11 February 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}