{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,20]],"date-time":"2025-11-20T12:22:37Z","timestamp":1763641357847},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540422259"},{"type":"electronic","value":"9783540455356"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-45535-3_5","type":"book-chapter","created":{"date-parts":[[2010,2,11]],"date-time":"2010-02-11T14:39:51Z","timestamp":1265899191000},"page":"60-70","source":"Crossref","is-referenced-by-count":15,"title":["Approximate k-MSTs and k-Steiner Trees via the Primal-Dual Method and Lagrangean Relaxation"],"prefix":"10.1007","author":[{"given":"Fabi\u00e1n A.","family":"Chudak","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tim","family":"Roughgarden","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David P.","family":"Williamson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,6,21]]},"reference":[{"key":"5_CR1","doi-asserted-by":"crossref","unstructured":"S. Arora and G. Karakostas. Approximation schemes for minimum latency problems. In Proceedings of the 31st Annual ACM Symposium on the Theory of Computing, pages 688\u2013693, 1999.","DOI":"10.1145\/301250.301432"},{"key":"5_CR2","unstructured":"S. Arora and G. Karakostas. A 2 + \u2208 approximation algorithm for the k-MST problem. In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 754\u2013759, 2000."},{"key":"5_CR3","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/S0020-0190(98)00010-6","volume":"65","author":"S. Arya","year":"1998","unstructured":"S. Arya and H. Ramesh. A 2.5-factor approximation algorithm for the k-MST problem. Information Processing Letters, 65:117\u2013118, 1998.","journal-title":"Information Processing Letters"},{"issue":"1","key":"5_CR4","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1137\/S009753979528826X","volume":"28","author":"B. Awerbuch","year":"1999","unstructured":"B. Awerbuch, Y. Azar, A. Blum, and S. Vempala. Improved approximation guarantees for minimum-weight k-trees and prize-collecting salesmen. SIAM Journal on Computing, 28(1):254\u2013262, 1999.","journal-title":". SIAM Journal on Computing"},{"key":"5_CR5","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0020-0190(89)90039-2","volume":"32","author":"M. Bern","year":"1989","unstructured":"M. Bern and P. Plassmann. The Steiner problem with edge lengths 1 and 2. Information Processing Letters, 32:171\u2013176, 1989.","journal-title":"Information Processing Letters"},{"key":"5_CR6","doi-asserted-by":"crossref","unstructured":"A. Blum, P. Chalasani, D. Coppersmith, W. Pulleyblank, P. Raghavan, and M. Sudan. The minimum latency problem. In Proceedings of the 26th Annual ACM Symposium on the Theory of Computing, pages 163\u2013171, 1994.","DOI":"10.1145\/195058.195125"},{"issue":"1","key":"5_CR7","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1006\/jcss.1997.1542","volume":"58","author":"A. Blum","year":"1999","unstructured":"A. Blum, R. Ravi, and S. Vempala. A constant-factor approximation algorithm for the k-MST problem. Journal of Computer and System Sciences, 58(1):101\u2013108, 1999.","journal-title":"Journal of Computer and System Sciences"},{"key":"5_CR8","doi-asserted-by":"crossref","unstructured":"M. Charikar and S. Guha. Improved combinatorial algorithms for the facility location and k-median problems. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science, pages 378\u2013388, 1999.","DOI":"10.1109\/SFFCS.1999.814609"},{"key":"5_CR9","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1002\/net.3230240103","volume":"24","author":"M. Fischetti","year":"1994","unstructured":"M. Fischetti, H. Hamacher, K. J\u00f8rnsten, and F. Maffioli. Weighted k-cardinality trees: Complexity and polyhedral structure. Networks, 24:11\u201321,1994.","journal-title":"Networks"},{"key":"5_CR10","doi-asserted-by":"crossref","unstructured":"N. Garg. A 3-approximation for the minimum tree spanning k vertices. In Proceedings of the 37th Annual Symposium on Foundations of Computer Science, pages 302\u2013309, 1996.","DOI":"10.1109\/SFCS.1996.548489"},{"key":"5_CR11","unstructured":"N. Garg. Personal communication, 1999."},{"key":"5_CR12","first-page":"111","volume":"82","author":"M. Goemans","year":"1998","unstructured":"M. Goemans and J. Kleinberg. An improved approximation ratio for the minimum latency problem. Mathematical Programming, 82:111\u2013124, 1998.","journal-title":"Mathematical Programming"},{"key":"5_CR13","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":"5_CR14","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":"5_CR15","doi-asserted-by":"crossref","unstructured":"K. Jain and V. V. Vazirani. Primal-dual approximation algorithms for metric facility location and k-median problems. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science, pages 2\u201313, 1999.","DOI":"10.1109\/SFFCS.1999.814571"},{"key":"5_CR16","unstructured":"S. Rajagopalan and Vijay V. Vazirani. Logarithmic approximation of minimum weight k trees. Unpublished manuscript, 1995."},{"key":"5_CR17","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1137\/S0895480194266331","volume":"9","author":"R. Ravi","year":"1996","unstructured":"R. Ravi, R. Sundaram, M. V. Marathe, D. J. Rosenkrantz, and S. S. Ravi. Spanning trees short or small. SIAM Journal on Discrete Mathematics, 9:178\u2013200, 1996.","journal-title":"SIAM Journal on Discrete Mathematics"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45535-3_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,24]],"date-time":"2019-02-24T10:57:09Z","timestamp":1551005829000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45535-3_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540422259","9783540455356"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-45535-3_5","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}