{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,27]],"date-time":"2025-08-27T15:36:14Z","timestamp":1756308974873},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2009,5,21]],"date-time":"2009-05-21T00:00:00Z","timestamp":1242864000000},"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":[[2009,10]]},"DOI":"10.1007\/s10878-009-9227-8","type":"journal-article","created":{"date-parts":[[2009,5,20]],"date-time":"2009-05-20T15:56:20Z","timestamp":1242834980000},"page":"258-271","source":"Crossref","is-referenced-by-count":10,"title":["A 6.55 factor primal-dual approximation algorithm for\u00a0the connected facility location problem"],"prefix":"10.1007","volume":"18","author":[{"given":"Hyunwoo","family":"Jung","sequence":"first","affiliation":[]},{"given":"Mohammad Khairul","family":"Hasan","sequence":"additional","affiliation":[]},{"given":"Kyung-Yong","family":"Chwa","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,5,21]]},"reference":[{"key":"9227_CR1","doi-asserted-by":"crossref","unstructured":"Byrka J (2007) An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem. In: APPROX-RANDOM, pp 29\u201343","DOI":"10.1007\/978-3-540-74208-1_3"},{"issue":"1","key":"9227_CR2","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):1\u201325","journal-title":"SIAM J Comput"},{"key":"9227_CR3","unstructured":"Eisenbrand F, Grandoni F, Rothvo\u00dfT, Sch\u00e4fer G (2008) Approximating connected facility location problems via random facility sampling and core detouring. In: SODA\u201908: Proceedings of the nineteenth annual ACM\u2013SIAM symposium on discrete algorithms, pp 1174\u20131183"},{"key":"9227_CR4","doi-asserted-by":"crossref","first-page":"296","DOI":"10.1137\/S0097539793242618","volume":"24","author":"MX Goemans","year":"1995","unstructured":"Goemans MX, Williamson DP (1995) A general approximation technique for constrained forest problems. SIAM J Comput 24:296\u2013317","journal-title":"SIAM J Comput"},{"key":"9227_CR5","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":"9227_CR6","doi-asserted-by":"crossref","unstructured":"Gupta A, Kleinberg J, Kumar A, Rastogi R, Yener B (2001) Provisioning a virtual private network: a network design problem for multicommodity flow. In: Proceedings of the 33rd annual ACM symposium on theory of computing, pp 389\u2013398","DOI":"10.1145\/380752.380830"},{"issue":"2","key":"9227_CR7","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1007\/s10878-007-9130-0","volume":"16","author":"MK Hasan","year":"2008","unstructured":"Hasan MK, Jung H, Chwa K-Y (2008) Approximation algorithms for connected facility location problems. J Comb Optim 16(2):155\u2013172","journal-title":"J Comb Optim"},{"key":"9227_CR8","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 the 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":"9227_CR9","doi-asserted-by":"crossref","unstructured":"Jain K, Mahdian M, Saberi A (2002) A new greedy approach for facility location problems. In: STOC\u201902: Proceedings of the thirty-fourth annual ACM symposium on theory of computing, pp 731\u2013740","DOI":"10.1145\/509907.510012"},{"key":"9227_CR10","doi-asserted-by":"crossref","unstructured":"Karger DR, Minkoff M (2000) Building steiner trees with incomplete global knowledge. In: FOCS\u201900: Proceedings of 41st annual symposium on foundations of computer science, pp 613\u2013623","DOI":"10.1109\/SFCS.2000.892329"},{"key":"9227_CR11","unstructured":"Korupolu MR, Plaxton CG, Rajaraman R (1998) Analysis of a local search heuristic for facility location problems. In: Proceedings of the 9th annual ACM\u2013SIAM symposium on discrete algorithms, pp 1\u201310"},{"key":"9227_CR12","doi-asserted-by":"crossref","unstructured":"Levi R, Shmoys DB, Swamy C (2004) LP-based approximation algorithms for capacitated facility location. In: Proceedings of IPCO, pp 206\u2013218","DOI":"10.1007\/978-3-540-25960-2_16"},{"key":"9227_CR13","doi-asserted-by":"crossref","unstructured":"Mahdian M, Pal M (2003) Universal facility location. In: Proceedings of 11th European symposium on algorithms, pp 409\u2013422","DOI":"10.1007\/978-3-540-39658-1_38"},{"key":"9227_CR14","doi-asserted-by":"crossref","unstructured":"Mahdian M, Ye Y, Zhang J (2002) Improved approximation algorithms for metric facility location problems. In: Proceedings of the 5th international workshop on approximation algorithms for combinatorial optimization, pp 229\u2013242","DOI":"10.1007\/3-540-45753-4_20"},{"key":"9227_CR15","doi-asserted-by":"crossref","unstructured":"Pal M, Tardos \u00c9, Wexler T (2001) Facility location with nonuniform hard capacities. In: Proceedings of the 42nd annual IEEE symposium on foundations of computer science, pp 329\u2013338","DOI":"10.1109\/SFCS.2001.959907"},{"key":"9227_CR16","unstructured":"Robins G, Zelikovsky A (2000) Improved Steiner tree approximation in graphs. In: Proceedings of the 11th annual ACM-SIAM symposium on discrete algorithms, pp 329\u2013338"},{"key":"9227_CR17","doi-asserted-by":"crossref","unstructured":"Shmoys DB, Tardos \u00c9, Aardal K (1997) Approximation algorithms for facility location problems (extended abstract). In: STOC\u201997: Proceedings of the twenty-ninth annual ACM symposium on theory on computing, pp 265\u2013274","DOI":"10.1145\/258533.258600"},{"key":"9227_CR18","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/s00453-004-1112-3","volume":"40","author":"C Swamy","year":"2004","unstructured":"Swamy C, Kumar A (2004) Primal-dual algorithms for connected facility location problems. Algorithmica 40:245\u2013269","journal-title":"Algorithmica"},{"issue":"6","key":"9227_CR19","doi-asserted-by":"crossref","first-page":"707","DOI":"10.1016\/j.orl.2007.02.005","volume":"35","author":"DP Williamson","year":"2007","unstructured":"Williamson DP, Zuylen A (2007) A simpler and better derandomization of an approximation algorithm for single source rent-or-buy. Oper Res Lett 35(6):707\u2013712","journal-title":"Oper Res Lett"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-009-9227-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-009-9227-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-009-9227-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T04:18:14Z","timestamp":1559276294000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-009-9227-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,5,21]]},"references-count":19,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2009,10]]}},"alternative-id":["9227"],"URL":"https:\/\/doi.org\/10.1007\/s10878-009-9227-8","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,5,21]]}}}