{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:42:32Z","timestamp":1781077352599,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540327554","type":"print"},{"value":"9783540327561","type":"electronic"}],"license":[{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11682462_4","type":"book-chapter","created":{"date-parts":[[2006,2,17]],"date-time":"2006-02-17T11:50:30Z","timestamp":1140177030000},"page":"13-24","source":"Crossref","is-referenced-by-count":9,"title":["Matching Based Augmentations for Approximating Connectivity Problems"],"prefix":"10.1007","author":[{"given":"R.","family":"Ravi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"4_CR1","unstructured":"Chekuri, C., Khanna, S., Naor, S.: A deterministic algorithm for the COSTDISTANCE problem. In: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 232\u2013233 (2001)"},{"key":"4_CR2","unstructured":"Christofides, N.: Worst-case analysis of a new heuristic for the travelling salesman problem. Report 388, Graduate School of Industrial Administration, CMU (1976)"},{"key":"4_CR3","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1002\/net.3230120103","volume":"12","author":"A.M. Frieze","year":"1982","unstructured":"Frieze, A.M., Galbiati, G., Maffioli, F.: On the worst-case performance of some algorithms for the asymmetric traveling salesman problem. Networks\u00a012, 23\u201339 (1982)","journal-title":"Networks"},{"key":"4_CR4","unstructured":"F\u00fcrer, M., Raghavachari, B.: An NC approximation algorithm for the minimumdegree spanning tree problem. In: Proceedings of the 28th Annual Allerton Conference on Communication, Control and Computing, pp. 274\u2013281 (1990)"},{"key":"4_CR5","unstructured":"Goel, Estrin, D.: Simultaneous Optimization for Concave Costs: Single Sink Aggregation or Single Source Buy-at-Bulk. In: Proceedings of the 14th Annual ACMSIAM Symposium on Discrete Algorithms (2003)"},{"key":"4_CR6","doi-asserted-by":"crossref","unstructured":"Hochbaum, D. (ed.): Approximation algorithms for NP-hard problems. P.W.S (1997)","DOI":"10.1145\/261342.571216"},{"issue":"1","key":"4_CR7","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1006\/jagm.1995.1029","volume":"19","author":"P.N. Klein","year":"1995","unstructured":"Klein, P.N., Ravi, R.: A nearly best-possible approximation algorithm for node-weighted Steiner trees. J. Algorithms\u00a019(1), 104\u2013115 (1995); An early version appeared in the Proceedings of the Annual MPS conference on Integer Programming and Combinatorial Optimization (1992)","journal-title":"J. Algorithms"},{"key":"4_CR8","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1006\/jagm.1998.0930","volume":"28","author":"M.V. Marathe","year":"1998","unstructured":"Marathe, M.V., Ravi, R., Sundaram, R., Ravi, S.S., Rosenkrantz, D.J., Hunt, H.B.: Bicriteria network design problems. J. of Algorithms\u00a028, 142\u2013171 (1998)","journal-title":"J. of Algorithms"},{"key":"4_CR9","doi-asserted-by":"crossref","unstructured":"Meyerson, A., Munagala, K., Plotkin, S.: Cost-Distance: Two Metric Network Design. In: Proceedings of the 41st Annual IEEE Symposium on the Foundations of Computer Science (2000)","DOI":"10.1109\/SFCS.2000.892330"},{"key":"4_CR10","doi-asserted-by":"crossref","unstructured":"Ravi, R., Marathe, M.V., Ravi, S.S., Rosenkrantz, D.J., Hunt III, H.B.: Many birds with one stone: Multi-objective approximation algorithms. In: Proceedings of the ACM Symposium on the Theory of Computing, pp. 438\u2013447 (1993)","DOI":"10.1145\/167088.167209"},{"key":"4_CR11","doi-asserted-by":"crossref","unstructured":"Ravi, R.: Rapid Rumor Ramification: Approximating the minimum broadcast time. In: Proceedings of the 35th Annual IEEE Symposium on the Foundations of Computer Science, pp. 202\u2013213 (1994)","DOI":"10.1109\/SFCS.1994.365693"},{"issue":"1","key":"4_CR12","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1007\/s00453-001-0038-2","volume":"31","author":"R. Ravi","year":"2001","unstructured":"Ravi, R., Marathe, M.V., Ravi, S.S., Rosenkrantz, D.J., Hunt III, H.B.: Approximation Algorithms for Degree-Constrained Minimum-Cost Network- Design Problems. Algorithmica\u00a031(1), 58\u201378 (2001)","journal-title":"Algorithmica"},{"key":"4_CR13","volume-title":"Approximation Algorithms","author":"V.V. Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Berlin (2001)"}],"container-title":["Lecture Notes in Computer Science","LATIN 2006: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11682462_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,17]],"date-time":"2019-04-17T00:18:48Z","timestamp":1555460328000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11682462_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540327554","9783540327561"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/11682462_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}