{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:58:38Z","timestamp":1725559118098},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540241317"},{"type":"electronic","value":"9783540305514"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-30551-4_22","type":"book-chapter","created":{"date-parts":[[2010,7,13]],"date-time":"2010-07-13T18:15:37Z","timestamp":1279044937000},"page":"234-245","source":"Crossref","is-referenced-by-count":0,"title":["The Polymatroid Steiner Problems"],"prefix":"10.1007","author":[{"given":"Gruia","family":"Calinescu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander","family":"Zelikovsky","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"doi-asserted-by":"crossref","unstructured":"Bartal, Y.: Probabilistic approximation of metric spaces and its algorithmic applications. In: FOCS (1996)","key":"22_CR1","DOI":"10.1109\/SFCS.1996.548477"},{"doi-asserted-by":"crossref","unstructured":"Bartal, Y.: On approximating arbitrary metrics by tree metrics. In: STOC (1998)","key":"22_CR2","DOI":"10.1145\/276698.276725"},{"doi-asserted-by":"crossref","unstructured":"Berman, P., Calinescu, G., Shah, C., Zelikovsky, A.: Power efficient monitoring management in sensor networks. In: Proc. IEEE Wireless Communications and Networking Conference (2004)","key":"22_CR3","DOI":"10.1109\/WCNC.2004.1311452"},{"doi-asserted-by":"crossref","unstructured":"Calinescu, G., Kapoor, S., Olshevsky, A., Zelikovsky, A.: Network lifetime and power assignment in ad-hoc wireless networks. In: Proc. 11th European Symphosium on Algorithms (2003)","key":"22_CR4","DOI":"10.1007\/978-3-540-39658-1_13"},{"unstructured":"Charikar, M., Chekuri, C., Goel, A., Guha, S.: Approximating a finite metric by a small number of tree metrics. In: STOC (1999)","key":"22_CR5"},{"issue":"1","key":"22_CR6","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1006\/jagm.1999.1042","volume":"33","author":"M. Charikar","year":"1999","unstructured":"Charikar, M., Chekuri, C., Cheung, T., Dai, Z., Goel, A., Guha, S., Li, M.: Approximation Algorithms for Directed Steiner Problems. Journal of Algorithms\u00a033(1), 73\u201391 (1999)","journal-title":"Journal of Algorithms"},{"unstructured":"Chekuri, C., Even, G., Kortsarz, G.: Acombinatorial approximation algorithm for the group Steiner problem, Submitted for publication. Available on the web (2002)","key":"22_CR7"},{"doi-asserted-by":"crossref","unstructured":"Even, G., Kortsarz, G., Slany, W.: On network design: fixed charge flows and the covering Steiner problem. In: SWAT, pp. 318\u2013329 (2002)","key":"22_CR8","DOI":"10.1007\/3-540-45471-3_33"},{"doi-asserted-by":"crossref","unstructured":"Fakcharoenphol, J., Rao, S., Talwar, K.: Atight bound on approximating arbitrary metrics by tree metrics. In: STOC (2003)","key":"22_CR9","DOI":"10.1145\/780542.780608"},{"issue":"1","key":"22_CR10","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1006\/jagm.2000.1096","volume":"37","author":"N. Garg","year":"2000","unstructured":"Garg, N., Konjevod, G., Ravi, R.: A polylogarithmic approximation algorithm for the group Steiner tree problem. J. Algorithms\u00a037(1), 66\u201384 (2000)","journal-title":"J. Algorithms"},{"doi-asserted-by":"crossref","unstructured":"Garg, N., Konemann, J.: Faster and simpler algorithms for multicommodity flow and other fractional packing problems. In: IEEE Symposium on Foundations of Computer Science, pp. 300\u2013309 (1998)","key":"22_CR11","DOI":"10.1109\/SFCS.1998.743463"},{"unstructured":"Halperin, E., Kortsarz, G., Krauthgamer, R., Srinivasan, A., Wang, N.: Integrality ratio for Group Steiner Trees and Directed Steiner Trees. In: 14th Annual ACM-SIAM Symposium on Discrete Algorithms, January, pp. 275\u2013284 (2003)","key":"22_CR12"},{"doi-asserted-by":"crossref","unstructured":"Halperin, E., Krauthgamer, R.: Polylogarithmic inapproximability. In: Proceedings of the 35th ACM Symposium on Theory of Computing, pp. 585\u2013594 (2003)","key":"22_CR13","DOI":"10.1145\/780542.780628"},{"issue":"1","key":"22_CR14","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1002\/1097-0037(200101)37:1<8::AID-NET2>3.0.CO;2-R","volume":"37","author":"C.H. Helvig","year":"2001","unstructured":"Helvig, C.H., Robins, G., Zelikovsky, A.: Improved approximation scheme for the group Steiner problem. Networks\u00a037(1), 8\u201320 (2001)","journal-title":"Networks"},{"issue":"3","key":"22_CR15","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1002\/rsa.10038","volume":"20","author":"G. Konjevod","year":"2002","unstructured":"Konjevod, G., Ravi, R., Srinivasan, A.: Approximation algorithms for the covering Steiner problem. Random Structures and Algorithms\u00a020(3), 465\u2013482 (2002); Preliminary version by Konjevod and Ravi in SODA (2000)","journal-title":"Random Structures and Algorithms"},{"unstructured":"Konjevod, G., Ravi, R.: An approximation algorithm for the covering steiner problem. In: Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, Society for Industrial and Applied Mathematics, pp. 338\u2013344 (2000)","key":"22_CR16"},{"key":"22_CR17","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/BF02579435","volume":"2","author":"L.A. Wolsey","year":"1982","unstructured":"Wolsey, L.A.: Analysis of the greedy algorithm for the submodular set covering problem. Combinatorica\u00a02, 385\u2013392 (1982)","journal-title":"Combinatorica"},{"doi-asserted-by":"crossref","unstructured":"Zelikovsky, A.: A series of approximation algorithms for the acyclic directed Steiner tree problem. Algorithmica\u00a018 (1997)","key":"22_CR18","DOI":"10.1007\/BF02523690"},{"unstructured":"Zosin, L., Khuller, S.: On directed Steiner trees. In: SODA, pp. 59\u201363 (2002)","key":"22_CR19"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30551-4_22.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T04:21:23Z","timestamp":1605759683000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-30551-4_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540241317","9783540305514"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30551-4_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}