{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,24]],"date-time":"2025-09-24T10:21:21Z","timestamp":1758709281656,"version":"3.37.3"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2017,9,30]],"date-time":"2017-09-30T00:00:00Z","timestamp":1506729600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"Higher Educational Science and Technology Program of Shandong Province","award":["J15LN22"],"award-info":[{"award-number":["J15LN22"]}]},{"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":["11531014"],"award-info":[{"award-number":["11531014"]}],"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":[[2018,2]]},"DOI":"10.1007\/s10878-017-0179-0","type":"journal-article","created":{"date-parts":[[2017,9,30]],"date-time":"2017-09-30T01:31:27Z","timestamp":1506735087000},"page":"409-423","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["A local search approximation algorithm for the uniform capacitated k-facility location problem"],"prefix":"10.1007","volume":"35","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":"Donglei","family":"Du","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,9,30]]},"reference":[{"key":"179_CR1","doi-asserted-by":"crossref","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$$ k -median and facility location problems. SIAM J Comput 33:544\u2013562","journal-title":"SIAM J Comput"},{"key":"179_CR2","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1007\/s10107-012-0565-4","volume":"141","author":"A Aggarwal","year":"2013","unstructured":"Aggarwal A, Louis A, Bansal M, Garg N, Gupta N, Gupta S, Jain S (2013) A $$3$$ 3 -approximation algorithm for the facility location problem with uniform capacities. Math Program 141:527\u2013547","journal-title":"Math Program"},{"key":"179_CR3","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 Oper Res 242:358\u2013368","journal-title":"Eur J Oper Res"},{"key":"179_CR4","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/BF01585522","volume":"7","author":"DA Babayev","year":"1974","unstructured":"Babayev DA (1974) Comments on the note of Frieze. Math Program 7:249\u2013252","journal-title":"Math Program"},{"key":"179_CR5","doi-asserted-by":"crossref","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":"179_CR6","unstructured":"Byrka J, Fleszar K, Rybicki B, Spoerhase J (2013) A constant-factor approximation algorithm for uniform hard capacitated $$k$$ k -median. CoRR, arXiv:1312.6550"},{"key":"179_CR7","unstructured":"Byrka J, Pensyl T, Rybicki B, Srinivasan A (2014) An improved approximation for $$k$$ k -median, and positive correlation in budgeted optimization. In: Proceedings of SODA, pp 737\u2013756"},{"key":"179_CR8","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","DOI":"10.1137\/1.9781611973730.49"},{"key":"179_CR9","unstructured":"Byrka J, Rybicki B, Uniyal S (2016) An approximation algorithm for uniform capacitated $$k$$ k -median problem with $$1+\\varepsilon $$ 1 + \u03b5 capacity violation. In: Proceedings of IPCO, pp 262\u2013274"},{"key":"179_CR10","doi-asserted-by":"crossref","first-page":"803","DOI":"10.1137\/S0097539701398594","volume":"34","author":"M Charikar","year":"2005","unstructured":"Charikar M, Guha S (2005) Improved combinatorial algorithms for facility location problems. SIAM J Comput 34:803\u2013824","journal-title":"SIAM J Comput"},{"key":"179_CR11","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1006\/jcss.2002.1882","volume":"1","author":"M Charikar","year":"2002","unstructured":"Charikar M, Guha S, Tardos E, Shmoys DB (2002) A constant-factor approximation algorithm for the $$k$$ k -median problem. J Comput Syst Sci 1:129\u2013149","journal-title":"J Comput Syst Sci"},{"key":"179_CR12","doi-asserted-by":"crossref","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":"179_CR13","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/s10107-004-0524-9","volume":"102","author":"FA Chudak","year":"2005","unstructured":"Chudak FA, Williamson DP (2005) Improved approximation algorithms for capacitated facility location problems. Math Program 102:207\u2013222","journal-title":"Math Program"},{"key":"179_CR14","unstructured":"Demirci G, Li S (2016) Constant approximation for capacitated $$k$$ k -median with $$(1+\\epsilon ) $$ ( 1 + \u03f5 ) -capacity violation. In: Proceedings of ICALP, Article No. 73, pp 73:1\u201373:14"},{"key":"179_CR15","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"},{"key":"179_CR16","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-dual schema and Lagrangian relaxation. J ACM 48:274\u2013296","journal-title":"J ACM"},{"key":"179_CR17","doi-asserted-by":"crossref","unstructured":"Jain K, Mahdian M, Saberi A (2002) A new greedy approach for facility location problems. In: Proceedings of STOC, pp 731\u2013740","DOI":"10.1145\/509907.510012"},{"key":"179_CR18","doi-asserted-by":"crossref","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 V (2003) Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. J ACM 50:795\u2013824","journal-title":"J ACM"},{"key":"179_CR19","doi-asserted-by":"crossref","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":"179_CR20","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1006\/jagm.2000.1100","volume":"37","author":"MR Korupolu","year":"2000","unstructured":"Korupolu MR, Plaxton CG, Rajaraman R (2000) Analysis of a local search heuristic for facility location problems. J Algorithms 37:146\u2013188","journal-title":"J Algorithms"},{"key":"179_CR21","doi-asserted-by":"crossref","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$$ 1.488 approximation algorithm for the uncapacitated facility location problem. Inf Comput 222:45\u201358","journal-title":"Inf Comput"},{"key":"179_CR22","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","DOI":"10.1137\/1.9781611973730.47"},{"key":"179_CR23","doi-asserted-by":"crossref","first-page":"530","DOI":"10.1137\/130938645","volume":"45","author":"S Li","year":"2016","unstructured":"Li S, Svensson O (2016) Approximating $$k$$ k -median via pseudo-approximation. SIAM J Comput 45:530\u2013547","journal-title":"SIAM J Comput"},{"key":"179_CR24","doi-asserted-by":"crossref","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":"179_CR25","doi-asserted-by":"crossref","unstructured":"Mahdian M, Ye Y, Zhang J (2002) Improved approximation algorithms for metric facility location problems. In: Proceedings of APPROX, pp 229\u2013242","DOI":"10.1007\/3-540-45753-4_20"},{"key":"179_CR26","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"GL Nemhauser","year":"1978","unstructured":"Nemhauser GL, Wolsey LA, Fisher ML (1978) An analysis of approximations for maximizing submodular set functions: I. Math Program 14:265\u2013294","journal-title":"Math Program"},{"key":"179_CR27","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":"179_CR28","unstructured":"Shmoys DB, Tardos E, Aardal K (1997) Approximation algorithms for facility location problems. In: Proceedings of SOTC, pp 265\u2013274"},{"key":"179_CR29","doi-asserted-by":"crossref","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":"179_CR30","doi-asserted-by":"crossref","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":"179_CR31","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":"179_CR32","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 Oper Res 30:389\u2013403","journal-title":"Math Oper Res"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-017-0179-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-017-0179-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-017-0179-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,4]],"date-time":"2019-10-04T00:01:51Z","timestamp":1570147311000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-017-0179-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,30]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,2]]}},"alternative-id":["179"],"URL":"https:\/\/doi.org\/10.1007\/s10878-017-0179-0","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2017,9,30]]}}}