{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T14:35:26Z","timestamp":1759847726369,"version":"3.35.0"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540850960"},{"type":"electronic","value":"9783540850977"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-85097-7_25","type":"book-chapter","created":{"date-parts":[[2008,8,19]],"date-time":"2008-08-19T07:18:26Z","timestamp":1219130306000},"page":"265-277","source":"Crossref","is-referenced-by-count":7,"title":["Improved Primal-Dual Approximation Algorithm for the Connected Facility Location Problem"],"prefix":"10.1007","author":[{"given":"Hyunwoo","family":"Jung","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohammad Khairul","family":"Hasan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kyung-Yong","family":"Chwa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"25_CR1","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s00453-004-1112-3","volume":"40","author":"C. Swamy","year":"2004","unstructured":"Swamy, C., Kumar, A.: Primal-dual algorithms for connected facility location problems. Algorithmica\u00a040, 245\u2013269 (2004)","journal-title":"Algorithmica"},{"key":"25_CR2","doi-asserted-by":"crossref","unstructured":"Shmoys, D.B., Tardos, \u00c9., Aardal, K.: Approximation algorithms for facility location problems (extended abstract). In: STOC 1997: Proceedings of the twenty-ninth annual ACM symposium on Theory on Computing, pp. 265\u2013274 (1997)","DOI":"10.1145\/258533.258600"},{"key":"25_CR3","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1137\/S0097539793242618","volume":"24","author":"M.X. Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: A general approximation technique for constrained forest problems. SIAM Journal on Computing\u00a024, 296\u2013317 (1995)","journal-title":"SIAM Journal on Computing"},{"key":"25_CR4","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1006\/jagm.1998.0993","volume":"31","author":"S. Guha","year":"1999","unstructured":"Guha, S., Khuller, S.: Greedy strikes back: improved facility location algorithms. Journal of Algorithms\u00a031, 228\u2013248 (1999)","journal-title":"Journal of Algorithms"},{"key":"25_CR5","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1145\/375827.375845","volume":"48","author":"K. Jain","year":"2001","unstructured":"Jain, K., Vazirani, V.V.: Approximation algorithms for the metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation. Journal of the ACM\u00a048, 274\u2013296 (2001)","journal-title":"Journal of the ACM"},{"key":"25_CR6","unstructured":"Korupolu, M.R., Plaxton, C.G., Rajaraman, R.: Analysis of a local search heuristic for facility location problems. In: Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1\u201310 (1998)"},{"key":"25_CR7","doi-asserted-by":"crossref","unstructured":"Mahdian, M., Ye, Y., Zhang, J.: Improved approximation algorithms for metric facility location problems. In: Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization, pp. 229\u2013242 (2002)","DOI":"10.1007\/3-540-45753-4_20"},{"key":"25_CR8","doi-asserted-by":"crossref","unstructured":"Byrka, J.: An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem. In: APPROX-RANDOM, pp. 29\u201343 (2007)","DOI":"10.1007\/978-3-540-74208-1_3"},{"key":"25_CR9","doi-asserted-by":"crossref","unstructured":"Jain, K., Mahdian, M., Saberi, A.: A new greedy approach for facility location problems. In: STOC 2002: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pp. 731\u2013740 (2002)","DOI":"10.1145\/509907.510012"},{"issue":"1","key":"25_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0097539703405754","volume":"33","author":"F.A. Chudak","year":"2003","unstructured":"Chudak, F.A., Shmoys, D.: Improved approximation algorithms for the uncapacitated facility location problem. SIAM Journal on Computing\u00a033(1), 1\u201325 (2003)","journal-title":"SIAM Journal on Computing"},{"key":"25_CR11","doi-asserted-by":"crossref","unstructured":"Pal, M., Tardos, E., Wexler, T.: Facility location with nonuniform hard capacities. In: Proceedings of The 42nd Annual IEEE Symposium on Foundations of Computer Science, pp. 329\u2013338 (2001)","DOI":"10.1109\/SFCS.2001.959907"},{"key":"25_CR12","doi-asserted-by":"crossref","unstructured":"Mahdian, M., Pal, M.: Universal facility location. In: Proceedings of 11the European Symposim on Algorithms, pp. 409\u2013422 (2003)","DOI":"10.1007\/978-3-540-39658-1_38"},{"key":"25_CR13","doi-asserted-by":"crossref","unstructured":"Karger, D.R., Minkoff, M.: Building steiner trees with incomplete global knowledge. In: FOCS 2000: Proceedings of 41st Annual Symposium on Foundations of Computer Science, pp. 613\u2013623 (2000)","DOI":"10.1109\/SFCS.2000.892329"},{"key":"25_CR14","doi-asserted-by":"crossref","unstructured":"Gupta, A., Kleinberg, J., Kumar, A., Rastogi, R., Yener, B.: 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 (2001)","DOI":"10.1145\/380752.380830"},{"key":"25_CR15","doi-asserted-by":"crossref","unstructured":"Hasan, M.K., Jung, H., Chwa, K.-Y.: Improved approximation algorithm for connected facility location problems. In: Proceedings of The First International Conference on Combinatorial Optimization and Applications, pp. 311\u2013322 (2007)","DOI":"10.1007\/978-3-540-73556-4_33"},{"key":"25_CR16","unstructured":"Eisenbrand, F., Grandoni, F., Rothvo\u00df, T., Sch\u00e4fer, G.: Approximating connected facility location problems via random facility sampling and core detouring. In: SODA 2008: Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 1174\u20131183 (2008)"},{"issue":"6","key":"25_CR17","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1016\/j.orl.2007.02.005","volume":"35","author":"D.P. Williamson","year":"2007","unstructured":"Williamson, D.P., van Zuylen, A.: A simpler and better derandomization of an approximation algorithm for single source rent-or-buy. Operations Research Letters\u00a035(6), 707\u2013712 (2007)","journal-title":"Operations Research Letters"},{"key":"25_CR18","unstructured":"Robins, G., Zelikovsky, A.: Improved Steiner tree approximation in graphs. In: Proceedings of The 11th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 329\u2013338 (2000)"},{"key":"25_CR19","doi-asserted-by":"crossref","unstructured":"Levi, R., Shmoys, D.B., Swamy, C.: LP-based spproximation slgorithms for capacitated facility location. In: Proceedings of IPCO, pp. 206\u2013218 (2004)","DOI":"10.1007\/978-3-540-25960-2_16"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-85097-7_25.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,31]],"date-time":"2025-01-31T15:28:00Z","timestamp":1738337280000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-85097-7_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540850960","9783540850977"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-85097-7_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}