{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T10:31:38Z","timestamp":1742639498616,"version":"3.37.3"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2017,10,23]],"date-time":"2017-10-23T00:00:00Z","timestamp":1508716800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11531014"],"award-info":[{"award-number":["11531014"]}],"id":[{"id":"10.13039\/501100001809","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":["11501412"],"award-info":[{"award-number":["11501412"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Higher Educational Science and Technology Program of Shandong Province","award":["J15LN22"],"award-info":[{"award-number":["J15LN22"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2018,2]]},"DOI":"10.1007\/s10878-017-0192-3","type":"journal-article","created":{"date-parts":[[2017,10,23]],"date-time":"2017-10-23T20:46:47Z","timestamp":1508791607000},"page":"493-511","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["An approximation algorithm for soft capacitated k-facility location problem"],"prefix":"10.1007","volume":"35","author":[{"given":"Yanjun","family":"Jiang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dachuan","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Donglei","family":"Du","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chenchen","family":"Wu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dongmei","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,10,23]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Aggarwal A, Anand L, Bansal M, Garg N, Gupta N, Gupta S, Jain S (2010) A 3-approximation for facility location with uniform capacities. In: Proceedings of IPCO, pp 149\u2013162","key":"192_CR1","DOI":"10.1007\/978-3-642-13036-6_12"},{"key":"192_CR2","doi-asserted-by":"crossref","first-page":"358","DOI":"10.1016\/j.ejor.2014.10.011","volume":"242","author":"K Aardal","year":"2015","unstructured":"Aardal K, van den Berg PL, Gijswijt D, Li S (2015) Approximation algorithms for hard capacitated $$k$$ k -facility location problems. Eur J Op Res 242:358\u2013368","journal-title":"Eur J Op Res"},{"key":"192_CR3","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1137\/S0895480102417215","volume":"18","author":"A Ageev","year":"2004","unstructured":"Ageev A, Ye Y, Zhang J (2004) Improved combinatorial approximation algorithm for the $$k$$ k -level facility location problem. SIAM J Discrete Math 18:207\u2013217","journal-title":"SIAM J Discrete Math"},{"doi-asserted-by":"crossref","unstructured":"Byrka J, Fleszar K, Rybicki B, Spoerhase J (2015) Bi-factor approximation algorithms for hard capacitated $$k$$ k -median problems. In: Proceedings of SODA, pp 722\u2013736","key":"192_CR4","DOI":"10.1137\/1.9781611973730.49"},{"doi-asserted-by":"crossref","unstructured":"Byrka J, Pensyl T, Rybicki B, Srinivasan A, Trinh K (2015) An improved approximation for $$k$$ k -median and positive correlation in budgeted optimization. In: Proceedings of SODA, pp 737\u2013756","key":"192_CR5","DOI":"10.1137\/1.9781611973730.50"},{"doi-asserted-by":"crossref","unstructured":"Byrka J, Rybicki B, Uniyal S (2016) An approximation algorithm for uniform capacitated $$k$$ k -median problem with $$1+\\epsilon $$ 1 + \u03f5 capacity violation. In: Proceedings of IPCO, pp 262-274","key":"192_CR6","DOI":"10.1007\/978-3-319-33461-5_22"},{"key":"192_CR7","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/s00453-007-9032-7","volume":"53","author":"X Chen","year":"2009","unstructured":"Chen X, Chen B (2009) Approximation algorithm for soft-capacitated facility location in capacitated network design. Algorithmica 53:263\u2013297","journal-title":"Algorithmica"},{"unstructured":"Charika M, Guha S, Tardos \u00c9, Shmoys D (1999) A constant-factor approximation algorithm for the $$k$$ k -median problem (extened abstract). In: Proceedings of STOC, pp 1\u201310","key":"192_CR8"},{"unstructured":"Chuzhoy J, Rabani Y (2005) Approximating $$k$$ k -median with non-uniform capacities. In: Proceedings of SODA, pp 952\u2013958","key":"192_CR9"},{"key":"192_CR10","doi-asserted-by":"crossref","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\u2013dual approximation algorithm for the facility location problem with submodular penalties. Algorithmica 63:191\u2013200","journal-title":"Algorithmica"},{"unstructured":"Gijswijt D, Li S (2013) Approximation algorithms for the capacitated $$k$$ k -facility location problems. arXiv:1311.4759","key":"192_CR11"},{"key":"192_CR12","doi-asserted-by":"crossref","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"},{"doi-asserted-by":"crossref","unstructured":"Guha S, Meyerson A, Munagala, K (2000) Hierarchical placement and network design problems. In: Proceedings of FOCS, pp 603\u2013612","key":"192_CR13","DOI":"10.1109\/SFCS.2000.892328"},{"key":"192_CR14","volume-title":"Approximation algorithms for NP-hard problems","author":"D Hochbaum","year":"1997","unstructured":"Hochbaum D (1997) Approximation algorithms for NP-hard problems. PWS Publishing Company, Boston"},{"key":"192_CR15","doi-asserted-by":"crossref","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$$ k -median problems using the primal\u2013dual schema and Lagrangian relaxation. J ACM 48:274\u2013296","journal-title":"J ACM"},{"key":"192_CR16","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1287\/mnsc.9.4.643","volume":"9","author":"A Kuehn","year":"1963","unstructured":"Kuehn A, Hamburger M (1963) A heuristic program for locating warehouses. Manage Sci 9:643\u2013666","journal-title":"Manage Sci"},{"doi-asserted-by":"crossref","unstructured":"Li S (2011) A $$1.488$$ 1.488 -approximation algorithm for the uncapacitated facility location problem. In: Proceedings of ICALP, Part 2, pp 77\u201388","key":"192_CR17","DOI":"10.1007\/978-3-642-22012-8_5"},{"doi-asserted-by":"crossref","unstructured":"Li S (2015) On uniform capacitated $$k$$ k -median beyond the natural LP relaxation. In: Proceedings of SODA, pp 696\u2013707","key":"192_CR18","DOI":"10.1137\/1.9781611973730.47"},{"unstructured":"Li S (2016) Approximating capacitated $$k$$ k -median with $$(1+\\epsilon )k$$ ( 1 + \u03f5 ) k open facilities. In: Proceedings of SODA, pp 786\u2013796","key":"192_CR19"},{"key":"192_CR20","volume-title":"Facilities location: models and methods","author":"R Love","year":"1988","unstructured":"Love R, Morris J, Wesolowsky G (1988) Facilities location: models and methods. North-Holland, New York"},{"doi-asserted-by":"crossref","unstructured":"Li S, Svensson O (2013) Approximating $$k$$ k -median via pseudo-approximation. In: Proceedings of STOC, pp 901\u2013910","key":"192_CR21","DOI":"10.1145\/2488608.2488723"},{"key":"192_CR22","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1137\/S0097539703435716","volume":"36","author":"M Mahdian","year":"2006","unstructured":"Mahdian M, Ye Y, Zhang J (2006) Approximation algorithm for metric facility location problem. SIAM J Comput 36:411\u2013432","journal-title":"SIAM J Comput"},{"unstructured":"Qiu L, Padmanabhan V, Voelker G (2001) On the placement of web server replicas. Proceedings of INFOCOM, vol. 3, pp 1587\u20131596","key":"192_CR23"},{"doi-asserted-by":"crossref","unstructured":"Shmoys D, Tard\u00f6s \u00c9, Aardal K (1997) Approximation algorithm for facility location problems. In: Proceedings of STOC, pp 265\u2013274","key":"192_CR24","DOI":"10.1145\/258533.258600"},{"key":"192_CR25","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1016\/j.tcs.2007.05.024","volume":"384","author":"P Zhang","year":"2007","unstructured":"Zhang P (2007) A new approximation algorithm for the $$k$$ k -facility location problem. Theor Comput Sci 384:126\u2013135","journal-title":"Theor Comput Sci"},{"key":"192_CR26","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1287\/moor.1040.0125","volume":"30","author":"J Zhang","year":"2005","unstructured":"Zhang J, Chen B, Ye Y (2005) A multiexchange local search algorithm for the capacitated facility location problem. Math Op Res 30:389\u2013403","journal-title":"Math Op Res"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-017-0192-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-017-0192-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-017-0192-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,4]],"date-time":"2019-10-04T21:58:06Z","timestamp":1570226286000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-017-0192-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,10,23]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,2]]}},"alternative-id":["192"],"URL":"https:\/\/doi.org\/10.1007\/s10878-017-0192-3","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2017,10,23]]}}}