{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:13:29Z","timestamp":1725484409938},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540438663"},{"type":"electronic","value":"9783540454717"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45471-3_33","type":"book-chapter","created":{"date-parts":[[2007,5,21]],"date-time":"2007-05-21T17:18:22Z","timestamp":1179767902000},"page":"318-327","source":"Crossref","is-referenced-by-count":8,"title":["On Network Design Problems: Fixed Cost Flows and the Covering Steiner Problem"],"prefix":"10.1007","author":[{"given":"Guy","family":"Even","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guy","family":"Kortsarz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wolfgang","family":"Slany","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,6,21]]},"reference":[{"unstructured":"S. Arora and C. Lund, \u201cHardness of Approximations\u201d, In Approximation Algorithms for NP-hard Problems, Dorit Hochbaum, Ed., PWS Publishing, 1996.","key":"33_CR1"},{"doi-asserted-by":"crossref","unstructured":"Y. Bartal, \u201dOn approximating arbitrary metrics by tree metrics\u201d, STOC, 1998.","key":"33_CR2","DOI":"10.1145\/276698.276725"},{"key":"33_CR3","first-page":"101","volume":"58","author":"A. Blum","year":"1999","unstructured":"A. Blum and R. Ravi and S. Vempala A constant-factor approximation algorithm for the k-MST Problem. JCSS, 58:101\u2013108, 1999.","journal-title":"JCSS"},{"key":"33_CR4","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1006\/jagm.1999.1042","volume":"33","author":"M. Charikar","year":"1999","unstructured":"M. Charikar, C. Chekuri, T. Cheung, Z. Dai, A. Goel, S. Guha and M. Li. \u201cApproximation Algorithms for directed Steiner Problems\u201d, J. of Algs., 33, p. 73\u201391, 1999.","journal-title":"J. of Algs."},{"unstructured":"M. Charikar, C. Chekuri, A. Goel, S. Guha, and S. Plotkin \u201cApproximating a finite metric by small number of trees\u201d, FOCS, 1998.","key":"33_CR5"},{"doi-asserted-by":"crossref","unstructured":"Y. Dodis and S. Khanna, \u201cDesigning Networks with bounded pairwise distance\u201d, STOC, 750\u2013759, 1999.","key":"33_CR6","DOI":"10.1145\/301250.301447"},{"unstructured":"M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, 1979.","key":"33_CR7"},{"unstructured":"N. Garg and G. Konjevod and R. Ravi, A polylogarithmic approximation algorithm for the group Steiner tree problem. SODA\u201998, pages 253\u2013259, 1998.","key":"33_CR8"},{"unstructured":"V. Guruswami, S. Khanna, R. Rajaraman, B. Shepherd and M. Yannakakis. Near-Optimal Hardness Results and Approximation Algorithms for Edge-Disjoint Paths and related Problems. STOC 99.","key":"33_CR9"},{"unstructured":"G. Konjevod and R. Ravi, An Approximation Algorithm for the Covering Steiner Problem. SODA 2000, 338\u2013334, 2000.","key":"33_CR10"},{"doi-asserted-by":"crossref","unstructured":"G. Konjevod, R. Ravi, and Aravind Srinivasan, Approximation Algorithms for the Covering Steiner Problem. manuscript, 2001.","key":"33_CR11","DOI":"10.1002\/rsa.10038"},{"key":"33_CR12","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/S0166-218X(99)00111-0","volume":"93","author":"G. Kortsarz","year":"1999","unstructured":"G. Kortsarz and D. Peleg. \u201cApproximating the Weight of Shallow Steiner Trees\u201d, Discrete Applied Math, vol 93, pages 265\u2013285, 1999.","journal-title":"Discrete Applied Math"},{"unstructured":"S.O. Krumke, H. Noltemeier, S. Schwarz, H.-C. Wirth and R. Ravi. Flow Improvement and Network Flows with Fixed Costs. OR-98, Z\u00fcrich, 1998.","key":"33_CR13"},{"doi-asserted-by":"crossref","unstructured":"R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge Univ. Press, 1995.","key":"33_CR14","DOI":"10.1017\/CBO9780511814075"},{"key":"33_CR15","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/BF02523690","volume":"18","author":"A. Zelikovsky","year":"1997","unstructured":"A. Zelikovsky. A series of approximation algorithms for the Acyclic directed Steiner Tree Problem. Algorithmica, 18:99\u2013110, 1997.","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT 2002"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45471-3_33","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,11]],"date-time":"2023-05-11T23:07:50Z","timestamp":1683846470000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45471-3_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540438663","9783540454717"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-45471-3_33","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}