{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,27]],"date-time":"2025-08-27T15:40:11Z","timestamp":1756309211060},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2008,1,3]],"date-time":"2008-01-03T00:00:00Z","timestamp":1199318400000},"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":[[2008,8]]},"DOI":"10.1007\/s10878-007-9130-0","type":"journal-article","created":{"date-parts":[[2008,1,2]],"date-time":"2008-01-02T15:21:49Z","timestamp":1199287309000},"page":"155-172","source":"Crossref","is-referenced-by-count":13,"title":["Approximation algorithms for connected facility location problems"],"prefix":"10.1007","volume":"16","author":[{"given":"Mohammad Khairul","family":"Hasan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hyunwoo","family":"Jung","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kyung-Yong","family":"Chwa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2008,1,3]]},"reference":[{"key":"9130_CR1","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":"9130_CR2","doi-asserted-by":"crossref","unstructured":"Grandoni F, Italiano G (2006) Improved approximation for single-sink buy-at-bulk. In: Proceedings of 17th international symposium on algorithms and computation (ISAAC), pp\u00a0111\u2013120","DOI":"10.1007\/11940128_13"},{"key":"9130_CR3","unstructured":"Guha S, Khuller S (1998) Greedy strikes back: Improved facility location algorithms. In: Proceedings of 9th annual ACM-SIAM symposium on discrete algorithms, pp\u00a0649\u2013657"},{"key":"9130_CR4","doi-asserted-by":"crossref","unstructured":"Gupta A, Kleinberg JM, Kumar A, Rastogi R, Yener B (2001) Provisioning a virtual private network: a network design problem for multicommodity flow. In: Proceedings of 33rd ACM symposium on theory of computing, pp\u00a0389\u2013398","DOI":"10.1145\/380752.380830"},{"key":"9130_CR5","doi-asserted-by":"crossref","unstructured":"Gupta A, Kumar A, Roughgarden T (2003) Simpler and better approximation algorithms for network design. In: Proceedings of 35th annual ACM symposium on theory of computing, New York, NY, USA, pp\u00a0365\u2013372","DOI":"10.1145\/780542.780597"},{"key":"9130_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) 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":"9130_CR7","doi-asserted-by":"crossref","unstructured":"Jothi R, Raghavachari B (2004) Improved approximation algorithms for the single-sink buy-at-bulk network design problems. In: Proceedings of 9th Scandinavian workshop on algorithm theory (SWAT), pp\u00a0336\u2013348","DOI":"10.1007\/978-3-540-27810-8_29"},{"key":"9130_CR8","unstructured":"Karger DR, Minkoff M (2000) Building steiner trees with incomplete global knowledge. In: Proceedings of 41st annual IEEE symposiam on foundations of computer science, Washington, DC, USA, pp\u00a0613\u2013623"},{"key":"9130_CR9","unstructured":"Korupolu MR, Plaxton CG, Rajaraman R (1998) Analysis of a local search heuristic for facility location problems. In: Proceedings of 9th annual ACM-SIAM symposium on discrete algorithms, pp\u00a01\u201310"},{"key":"9130_CR10","unstructured":"Lin J, Vitter JS (1992) \u03b5-approximations with minimum packing constraint violation. In: Proceedings of 24th ACM symposium on theory of computing, pp\u00a0771\u2013782"},{"key":"9130_CR11","doi-asserted-by":"crossref","unstructured":"Mahdian M, Ye Y, Zhang J (2002) Improved approximation algorithms for metric facility location problems. In: Proceedings of 5th international Workshop on approximation algorithms for combinatorial optimization, pp\u00a0229\u2013242","DOI":"10.1007\/3-540-45753-4_20"},{"key":"9130_CR12","unstructured":"Robins G, Zelikovsky A (2007) Improved Steiner tree approximation in graphs. In: Proceedings of 11th annual ACM-SIAM symposium on discrete algorithms, pp\u00a0770\u2013779"},{"key":"9130_CR13","doi-asserted-by":"crossref","unstructured":"Shmoys DB, Tardos \u00c9, Aardal K (1997) Approximation algorithms for facility location problems (extended abstract). In: Proceedings of 29th ACM symposium on theory of computing, pp\u00a0265\u2013274","DOI":"10.1145\/258533.258600"},{"key":"9130_CR14","doi-asserted-by":"crossref","unstructured":"Swamy C, Kumar A (2002) Primal-dual algorithms for connected facility location problems. In: Proceedings of 5th APPROX. LNCS, vol. 2462, pp\u00a0256\u2013269","DOI":"10.1007\/3-540-45753-4_22"},{"key":"9130_CR15","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"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-007-9130-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-007-9130-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-007-9130-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T04:18:12Z","timestamp":1559276292000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-007-9130-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1,3]]},"references-count":15,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,8]]}},"alternative-id":["9130"],"URL":"https:\/\/doi.org\/10.1007\/s10878-007-9130-0","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,1,3]]}}}