{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T15:16:17Z","timestamp":1787498177419,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540438663","type":"print"},{"value":"9783540454717","type":"electronic"}],"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-21T13:18:22Z","timestamp":1179753502000},"page":"318-327","source":"Crossref","is-referenced-by-count":9,"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":[{"vocabulary":"crossref","role":"author"}]},{"given":"Guy","family":"Kortsarz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wolfgang","family":"Slany","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2002,6,21]]},"reference":[{"key":"33_CR1","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_CR2","doi-asserted-by":"crossref","unstructured":"Y. Bartal, \u201dOn approximating arbitrary metrics by tree metrics\u201d, STOC, 1998.","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."},{"key":"33_CR5","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_CR6","doi-asserted-by":"crossref","unstructured":"Y. Dodis and S. Khanna, \u201cDesigning Networks with bounded pairwise distance\u201d, STOC, 750\u2013759, 1999.","DOI":"10.1145\/301250.301447"},{"key":"33_CR7","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_CR8","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_CR9","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_CR10","unstructured":"G. Konjevod and R. Ravi, An Approximation Algorithm for the Covering Steiner Problem. SODA 2000, 338\u2013334, 2000."},{"key":"33_CR11","doi-asserted-by":"crossref","unstructured":"G. Konjevod, R. Ravi, and Aravind Srinivasan, Approximation Algorithms for the Covering Steiner Problem. manuscript, 2001.","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"},{"key":"33_CR13","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_CR14","doi-asserted-by":"crossref","unstructured":"R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge Univ. Press, 1995.","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-11T19:07:50Z","timestamp":1683832070000},"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":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2002]]}}}