{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T06:55:42Z","timestamp":1760424942276},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2009,1,27]],"date-time":"2009-01-27T00:00:00Z","timestamp":1233014400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2010,11]]},"DOI":"10.1007\/s10878-009-9213-1","type":"journal-article","created":{"date-parts":[[2009,1,26]],"date-time":"2009-01-26T10:48:28Z","timestamp":1232966908000},"page":"361-368","source":"Crossref","is-referenced-by-count":15,"title":["An approximation algorithm for the k-level capacitated facility location problem"],"prefix":"10.1007","volume":"20","author":[{"given":"Donglei","family":"Du","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xing","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dachuan","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,1,27]]},"reference":[{"key":"9213_CR1","doi-asserted-by":"crossref","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":"9213_CR2","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1137\/S0895480102417215","volume":"18","author":"A Ageev","year":"2005","unstructured":"Ageev A, Ye Y, Zhang J (2005) Improved combinatorial approximation algorithms for the k-level facility location problem. SIAM J Discrete Math 18:207\u2013217","journal-title":"SIAM J Discrete Math"},{"key":"9213_CR3","doi-asserted-by":"crossref","unstructured":"Byrka J, Aardal KI (2009) An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem, SIAM J Comput (to appear)","DOI":"10.1137\/070708901"},{"key":"9213_CR4","unstructured":"Chudak FA, Williamson DP (1999) Improved approximation algorithms for capacitied facility location problems. In: Proceedings of IPCO 1999, pp 99\u2013113"},{"key":"9213_CR5","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1006\/jagm.1998.0993","volume":"31","author":"S Guha","year":"1999","unstructured":"Guha S, Kuller S (1999) Greedy strikes back: improved facility location algorithms. J Algorithms 31:228\u2013248","journal-title":"J Algorithms"},{"key":"9213_CR6","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) Primal-dual approximation algorithms for metric facility location and k-median problems. J ACM 48:274\u2013296","journal-title":"J ACM"},{"key":"9213_CR7","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 VV (2003) Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. J ACM 50:795\u2013824","journal-title":"J ACM"},{"key":"9213_CR8","unstructured":"Korupolu MR, Plaxton CG, Rajaraman R (1998) Analysis of a local search heuristic for facility location problems. In: Proceedings of SODA 1998, pp 1\u201310"},{"key":"9213_CR9","unstructured":"Levi R, Shmoys DB, Swamy C (2004) LP-based approximation algorithms for capacitated facility location (extended abstract). In: Proceedings of IPCO 2004, pp 206\u2013218"},{"key":"9213_CR10","doi-asserted-by":"crossref","unstructured":"Mahdian M, Pal M (2003) Universal facility location. In: Proceedings of ESA 2003, pp 409\u2013421","DOI":"10.1007\/978-3-540-39658-1_38"},{"key":"9213_CR11","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 algorithms for metric facility location problems. SIAM J Comput 36:411\u2013432","journal-title":"SIAM J Comput"},{"key":"9213_CR12","unstructured":"Pal M, Tardos E, Wexler T (2001) Facility location with hard capacities. In: Proceedings of FOCS 2001, pp 329\u2013338"},{"key":"9213_CR13","doi-asserted-by":"crossref","unstructured":"Shmoys DB, Tardos E, Aardal KI (1997) Approximation algorithms for facility location problems. In: Proceedings of STOC 1997, pp 265\u2013274","DOI":"10.1145\/258533.258600"},{"key":"9213_CR14","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1016\/j.orl.2005.06.002","volume":"34","author":"D Xu","year":"2006","unstructured":"Xu D, Du D (2006) The k-level facility location game. Oper Res Lett 34:421\u2013426","journal-title":"Oper Res Lett"},{"key":"9213_CR15","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1016\/j.orl.2007.04.002","volume":"36","author":"D Xu","year":"2008","unstructured":"Xu D, Zhang S (2008) Approximation algorithm for facility location with service installation costs. Oper Res Lett 36:46\u201350","journal-title":"Oper Res Lett"},{"key":"9213_CR16","doi-asserted-by":"crossref","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"},{"key":"9213_CR17","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\/content\/pdf\/10.1007\/s10878-009-9213-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-009-9213-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-009-9213-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T00:18:13Z","timestamp":1559261893000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-009-9213-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1,27]]},"references-count":17,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,11]]}},"alternative-id":["9213"],"URL":"https:\/\/doi.org\/10.1007\/s10878-009-9213-1","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,1,27]]}}}