{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,24]],"date-time":"2025-05-24T05:04:17Z","timestamp":1748063057734},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540441861"},{"type":"electronic","value":"9783540457534"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45753-4_22","type":"book-chapter","created":{"date-parts":[[2007,8,16]],"date-time":"2007-08-16T07:37:09Z","timestamp":1187249829000},"page":"256-270","source":"Crossref","is-referenced-by-count":32,"title":["Primal-Dual Algorithms for Connected Facility Location Problems"],"prefix":"10.1007","author":[{"given":"Chaitanya","family":"Swamy","sequence":"first","affiliation":[]},{"given":"Amit","family":"Kumar","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,10,4]]},"reference":[{"issue":"3","key":"22_CR1","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1137\/S0097539792236237","volume":"24","author":"A. Agrawal","year":"1995","unstructured":"A. Agrawal, P. Klein, and R. Ravi. When trees collide: An approximation algorithm for the generalized Steiner problem on networks. SIAM Journal on Computing, 24(3):440\u2013456, 1995.","journal-title":"SIAM Journal on Computing"},{"key":"22_CR2","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1137\/S0097539793242618","volume":"24","author":"M. X. Goemans","year":"1995","unstructured":"M. X. Goemans and D. P. Williamson. A general approximation technique for constrained forest problems. SIAM Journal on Computing, 24:296\u2013317, 1995.","journal-title":"SIAM Journal on Computing"},{"key":"22_CR3","unstructured":"M. X. Goemans and D. P. Williamson. The primal-dual method for approximation algorithms and its application to network design problems. In D. S. Hochbaum, editor, Approximation Algorithms for NP-Hard Problems, chapter 4, pages 144\u2013191. PWS Publishing Company, 1997."},{"key":"22_CR4","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1090\/dimacs\/040\/12","volume":"40","author":"S. Guha","year":"1997","unstructured":"S. Guha and S. Khuller. Connected facility location problems. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 40:179\u2013190, 1997.","journal-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science"},{"key":"22_CR5","doi-asserted-by":"crossref","unstructured":"A. Gupta, J. Kleinberg, A. Kumar, R. Rastogi, and B. Yener. Provisioning a virtual private network: A network design problem for multicommodity flow. In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC), pages 389\u2013398, 2001.","DOI":"10.1145\/380752.380830"},{"key":"22_CR6","doi-asserted-by":"crossref","unstructured":"R. Hassin, R. Ravi, and F. S. Selman. Approximation algorithms for a capacitated network design problem. In Proceedings of 4th APPROX, pages 167\u2013176, 2000.","DOI":"10.1007\/3-540-44436-X_17"},{"key":"22_CR7","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1145\/375827.375845","volume":"48","author":"K. Jain","year":"2001","unstructured":"K. Jain and V. V. Vazirani. Primal-dual approximation algorithms for metric facility location and k-median problems. Journal of the ACM, 48:274\u2013296, 2001.","journal-title":"Journal of the ACM"},{"key":"22_CR8","doi-asserted-by":"crossref","unstructured":"D. R. Karger and M. Minko.. Building Steiner trees with incomplete global knowledge. In Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 613\u2013623, 2000.","DOI":"10.1109\/SFCS.2000.892329"},{"key":"22_CR9","doi-asserted-by":"crossref","unstructured":"S. Khuller and A. Zhu. The general Steiner tree-star problem. Information Processing Letters, 2002. To appear.","DOI":"10.1016\/S0020-0190(02)00271-5"},{"issue":"3","key":"22_CR10","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1002\/(SICI)1097-0037(199610)28:3<167::AID-NET5>3.0.CO;2-L","volume":"28","author":"T. U. Kim","year":"1996","unstructured":"Tae Ung Kim, Timothy J. Lowe, Arie Tamir, and James E. Ward. On the location of a tree-shaped facility. Networks, 28(3):167\u2013175, 1996.","journal-title":"Networks"},{"key":"22_CR11","doi-asserted-by":"crossref","unstructured":"A. Kumar, A. Gupta, and T. Roughgarden. A constant-factor approximation algorithm for the multicommodity rent-or-buy problem. In Proceedings of the 43\n                        rd\n                         Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2002. To appear.","DOI":"10.1109\/SFCS.2002.1181956"},{"key":"22_CR12","unstructured":"M. Labb\u00e9, G. Laporte, I. Rodr\u00edgues Martin, and J. J. Salazar Gonz\u00e1lez. The median cycle problem. Technical Report 2001\/12, Department of Operations Research and Multicriteria Decision Aid at Universit\u00e9 Libre de Bruxelles, 2001."},{"issue":"3","key":"22_CR13","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1287\/ijoc.8.3.194","volume":"8","author":"Y. Lee","year":"1996","unstructured":"Y. Lee, S. Y. Chiu, and J. Ryan. A branch and cut algorithm for a Steiner tree-star problem. INFORMS Journal on Computing, 8(3):194\u2013201, 1996.","journal-title":"INFORMS Journal on Computing"},{"volume-title":"Discrete Location Theory","year":"1990","key":"22_CR14","unstructured":"P. Mirchandani and R. Francis, eds. Discrete Location Theory. John Wiley and Sons, Inc., New York, 1990."},{"key":"22_CR15","doi-asserted-by":"crossref","unstructured":"R. Ravi and A. Sinha. Integrated logistics: Approximation algorithms combining facility location and network design. In Proceedings of 9th IPCO, pages 212\u2013229, 2002.","DOI":"10.1007\/3-540-47867-1_16"},{"key":"22_CR16","unstructured":"G. Robins and A. Zelikovsky. Improved steiner tree approximation in graphs. In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 770\u2013779, 2000."},{"issue":"3","key":"22_CR17","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1007\/s101070100262","volume":"91","author":"D. P. Williamson","year":"2002","unstructured":"D. P. Williamson. The primal-dual method for approximation algorithms. Mathematical Programming, Series B, 91(3):447\u2013478, 2002.","journal-title":"Mathematical Programming, Series B"}],"container-title":["Lecture Notes in Computer Science","Approximation Algorithms for Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45753-4_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,1,24]],"date-time":"2019-01-24T15:32:28Z","timestamp":1548343948000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45753-4_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540441861","9783540457534"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-45753-4_22","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}