{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T11:41:59Z","timestamp":1773402119100,"version":"3.50.1"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2005,5,1]],"date-time":"2005-05-01T00:00:00Z","timestamp":1114905600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2005,5]]},"DOI":"10.1007\/s10878-005-1412-9","type":"journal-article","created":{"date-parts":[[2005,6,28]],"date-time":"2005-06-28T20:57:18Z","timestamp":1119992238000},"page":"281-294","source":"Crossref","is-referenced-by-count":24,"title":["The Polymatroid Steiner Problems"],"prefix":"10.1007","volume":"9","author":[{"given":"G.","family":"Calinescu","sequence":"first","affiliation":[]},{"given":"A.","family":"Zelikovsky","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"1412_CR1","unstructured":"Y. Bartal, \u201cProbabilistic approximation of metric spaces and its algorithmic applications,\u201d in FOCS, 1996."},{"key":"1412_CR2","doi-asserted-by":"crossref","unstructured":"Y. Bartal, \u201cOn approximating arbitrary metrics by tree metrics,\u201d in STOC, 1998.","DOI":"10.1145\/276698.276725"},{"key":"1412_CR3","doi-asserted-by":"crossref","unstructured":"P. Berman, G. Calinescu, C. Shah, and A. Zelikovsky, \u201cPower efficient monitoring management in sensor networks,\u201d in Proc. IEEE Wireless Communications and Networking Conference, 2004.","DOI":"10.1109\/WCNC.2004.1311452"},{"key":"1412_CR4","doi-asserted-by":"crossref","unstructured":"G. Calinescu, S. Kapoor, A. Olshevsky, and A. Zelikovsky, \u201cNetwork lifetime and power assignment in ad-hoc wireless networks,\u201d in Proc. 11th European Symposium on Algorithms, 2003.","DOI":"10.1007\/978-3-540-39658-1_13"},{"key":"1412_CR5","unstructured":"M. Charikar, C. Chekuri, A. Goel, and S. Guha, \u201cApproximating a finite metric by a small number of tree metrics,\u201d in STOC, 1999."},{"issue":"1","key":"1412_CR6","doi-asserted-by":"crossref","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 Journal of Algorithms, vol. 33, no. 1, pp. 73\u201391, 1999.","journal-title":"Journal of Algorithms"},{"key":"1412_CR7","unstructured":"C. Chekuri, G. Even, and G. Kortsarz, \u201cA combinatorial approximation algorithm for the group Steiner problem,\u201d 2002. Submitted for publication. Available on the web."},{"key":"1412_CR8","doi-asserted-by":"crossref","unstructured":"G. Even, G. Kortsarz, and W. Slany, \u201cOn network design: Fixed charge flows and the covering Steiner problem,\u201d in SWAT 2002, pp. 318\u2013329, 2002.","DOI":"10.1007\/3-540-45471-3_33"},{"key":"1412_CR9","doi-asserted-by":"crossref","unstructured":"J. Fakcharoenphol, S. Rao, and K. Talwar, \u201cA tight bound on approximating arbitrary metrics by tree metrics,\u201d in STOC, 2003.","DOI":"10.1145\/780542.780608"},{"issue":"1","key":"1412_CR10","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1006\/jagm.2000.1096","volume":"37","author":"N. Garg","year":"2000","unstructured":"N. Garg, G. Konjevod, and R. Ravi, \u201cA polylogarithmic approximation algorithm for the Group Steiner Tree problem,\u201d J. Algorithms, vol. 37, no. 1, pp, 66\u201384, 2000.","journal-title":"J. Algorithms"},{"key":"1412_CR11","doi-asserted-by":"crossref","unstructured":"N. Garg and J. Konemann, \u201cFaster and simpler algorithms for multicommodity flow and other fractional packing problems,\u201d in IEEE Symposium on Foundations of Computer Science, 1998, pp. 300\u2013309.","DOI":"10.1109\/SFCS.1998.743463"},{"key":"1412_CR12","doi-asserted-by":"crossref","unstructured":"A. Gupta and A Srinivasan, \u201cOn the covering steiner problem,\u201d in em Proc. Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2003, pp. 244\u2013251.","DOI":"10.1007\/978-3-540-24597-1_21"},{"key":"1412_CR13","unstructured":"E. Halperin, G. Kortsarz, R. Krauthgamer, A. Srinivasan, and N. Wang, \u201cIntegrality ratio for Group Steiner Trees and Directed Steiner Trees,\u201d in 14th Annual ACM-SIAM Symposium on Discrete Algorithms, Jan 2003, pp. 275\u2013284."},{"key":"1412_CR14","doi-asserted-by":"crossref","unstructured":"E. Halperin and R. Krauthgamer, \u201cPolylogarithmic inapproximability,\u201d in Proceedings of the 35th ACM Symposium on Theory of Computing, 2003, pp. 585\u2013594.","DOI":"10.1145\/780542.780628"},{"issue":"1","key":"1412_CR15","doi-asserted-by":"crossref","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":"C. H. Helvig, G. Robins, and A. Zelikovsky, \u201cImproved approximation scheme for the group Steiner problem,\u201d Networks, vol. 37, no. 1, pp. 8\u201320, 2001.","journal-title":"Networks"},{"key":"1412_CR16","doi-asserted-by":"crossref","unstructured":"G. Konjevod, R. Ravi, and A. Srinivasan. \u201cApproximation algorithms for the covering Steiner problem,\u201d Random Structures and Algorithms, vol. 20, no. 3, pp. 465\u2013482, 2002. Preliminary version by Konjevod and Ravi in SODA 2000.","DOI":"10.1002\/rsa.10038"},{"key":"1412_CR17","unstructured":"G. Konjevod and R. Ravi, \u201cAn approximation algorithm for the covering Steiner problem,\u201d in Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2000, pp. 338\u2013344."},{"key":"1412_CR18","doi-asserted-by":"crossref","unstructured":"L.A. Wolsey, \u201cAnalysis of the greedy algorithm for the submodular set covering problem,\u201d Combinatorica, vol. 2, no. 385\u2013392, 1982.","DOI":"10.1007\/BF02579435"},{"key":"1412_CR19","doi-asserted-by":"crossref","unstructured":"A. Zelikovsky, \u201cA series of approximation algorithms for the acyclic Directed Steiner Tree problem,\u201d Algorithmica, vol. 18, 1997.","DOI":"10.1007\/BF02523690"},{"key":"1412_CR20","unstructured":"L. Zosin and S. Khuller, \u201cOn Directed Steiner Trees,\u201d in SODA, 2002, pp. 59\u201363."}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-005-1412-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-005-1412-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-005-1412-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T01:35:49Z","timestamp":1586309749000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-005-1412-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,5]]},"references-count":20,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2005,5]]}},"alternative-id":["1412"],"URL":"https:\/\/doi.org\/10.1007\/s10878-005-1412-9","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,5]]}}}