{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:51:42Z","timestamp":1725486702774},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540679967"},{"type":"electronic","value":"9783540444367"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44436-x_22","type":"book-chapter","created":{"date-parts":[[2007,6,18]],"date-time":"2007-06-18T09:33:14Z","timestamp":1182159194000},"page":"214-225","source":"Crossref","is-referenced-by-count":7,"title":["Primal-Dual Approaches to the Steiner Problem"],"prefix":"10.1007","author":[{"given":"Tobias","family":"Polzin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Siavash","family":"Vahdati","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,6,3]]},"reference":[{"key":"22_CR1","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1002\/net.3230100207","volume":"10","author":"Y. P. Aneja","year":"1980","unstructured":"Y. P. Aneja. An integer linear programming approach to the Steiner problem in graphs. Networks, 10:167\u2013178, 1980.","journal-title":"Networks"},{"key":"22_CR2","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1287\/ijoc.4.3.320","volume":"4","author":"S. Chopra","year":"1992","unstructured":"S. Chopra, E. R. Gorres, and M. R. Rao. Solving the Steiner tree problem on a graph using branch and cut. ORSA Journal on Computing, 4:320\u2013335, 1992.","journal-title":"ORSA Journal on Computing"},{"key":"22_CR3","doi-asserted-by":"crossref","unstructured":"S. Chopra and M. R. Rao. The Steiner tree problem I: Formulations, compositions and extension of facets. Mathematical Programming, pages 209\u2013229, 1994.","DOI":"10.1007\/BF01582573"},{"key":"22_CR4","unstructured":"T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. MIT Press, 1990."},{"key":"22_CR5","unstructured":"C. W. Duin. Steiner\u2019s Problem in Graphs. PhD thesis, Amsterdam University, 1993."},{"key":"22_CR6","unstructured":"H. N. Gabow, M. X. Goemans, and D. P. Williamson. An efficient approximation algorithm for the survivable network design problem. In Proceedings 3rd Symposium on Integer Programming and Combinatorial Opt., pages 57\u201374, 1993."},{"key":"22_CR7","unstructured":"M. X. Goemans. Personal communication, 1998."},{"key":"22_CR8","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/BF01580607","volume":"60","author":"M. X. Goemans","year":"1993","unstructured":"M. X. Goemans and D. J. Bertsimas. Survivable networks, linear programming relaxations and the parsimonious property. Mathematical Programming, 60:145\u2013166, 1993.","journal-title":"Mathematical Programming"},{"key":"22_CR9","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1002\/net.3230230104","volume":"23","author":"M. X. Goemans","year":"1993","unstructured":"M. X. Goemans and Y. Myung. A catalog of Steiner tree formulations. Networks, 23:19\u201328, 1993.","journal-title":"Networks"},{"issue":"2","key":"22_CR10","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(2):296\u2013317, 1995.","journal-title":"SIAM Journal on Computing"},{"key":"22_CR11","unstructured":"M. X. Goemans and D. P. Williamson. The primal-dual method for approximation algorithms and its application to network design problem. In D. S. Hochbaum, editor, Approximation Algorithms for NP-hard Problems. PWS, 1996."},{"key":"22_CR12","unstructured":"F. K. Hwang, D. S. Richards, and P. Winter. The Steiner Tree Problem, volume 53 of Annals of Discrete Mathematics. North-Holland, Amsterdam, 1992."},{"issue":"6","key":"22_CR13","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/0020-0190(94)00156-1","volume":"52","author":"P. N. Klein","year":"1994","unstructured":"P. N. Klein. A data structure for bicategories, with application to speeding up an approximation algorithm. Information Processing Letters, 52(6):303\u2013307, 1994.","journal-title":"Information Processing Letters"},{"key":"22_CR14","unstructured":"T. Koch and A. Martin. SteinLib. ftp:\/\/ftp.zib.de\/pub\/Packages\/mp-testdata\/steinlib\/index.html , 1997."},{"key":"22_CR15","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1002\/(SICI)1097-0037(199810)32:3<207::AID-NET5>3.0.CO;2-O","volume":"32","author":"T. Koch","year":"1998","unstructured":"T. Koch and A. Martin. Solving Steiner tree problems in graphs to optimality. Networks, 32:207\u2013232, 1998.","journal-title":"Networks"},{"key":"22_CR16","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/0020-0190(88)90066-X","volume":"27","author":"Mehlhorn","year":"1988","unstructured":"Mehlhorn. A faster approximation algorithm for the Steiner problem in graphs. Information Processing Letters, 27:125\u2013128, 1988.","journal-title":"Information Processing Letters"},{"key":"22_CR17","unstructured":"T. Polzin and S. Vahdati Daneshmand. A comparison of Steiner tree relaxations. Technical Report 5\/1998, Universit\u00e4t Mannheim, 1998. (to appear in Discrete Applied Mathematics)."},{"key":"22_CR18","unstructured":"T. Polzin and S. Vahdati Daneshmand. Improved Algorithms for the Steiner Problem in Networks. Technical Report 06\/1998, Universit\u00e4t Mannheim, 1998. (to appear in Discrete Applied Mathematics)."},{"key":"22_CR19","doi-asserted-by":"crossref","unstructured":"T. Polzin and S. Vahdati Daneshmand. Primal-Dual Approaches to the Steiner Problem. Technical Report 14\/2000, Universit\u00e4t Mannheim, 2000.","DOI":"10.1007\/3-540-44436-X_22"},{"key":"22_CR20","unstructured":"S. Rajagopalan and V. V. Vazirani. On the bidirected cut relaxation for the metric Steiner tree problem. In Proceedings of the 10th ACM-SIAM Symposium on Discrete Algorithms, pages 742\u2013751, 1999."},{"key":"22_CR21","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/0166-218X(92)90021-2","volume":"40","author":"S. Vo\\","year":"1992","unstructured":"S. Vo\\. Steiner\u2019s problem in graphs: Heuristic methods. Discrete Applied Mathematics, 40:45\u201372, 1992.","journal-title":"Discrete Applied Mathematics"},{"key":"22_CR22","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/BF02612335","volume":"28","author":"R. T. Wong","year":"1984","unstructured":"R. T. Wong. A dual ascent approach for Steiner tree problems on a directed graph. Mathematical Programming, 28:271\u2013287, 1984.","journal-title":"Mathematical Programming"}],"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-44436-X_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,29]],"date-time":"2019-04-29T03:55:12Z","timestamp":1556510112000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44436-X_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540679967","9783540444367"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-44436-x_22","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}