{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:24:19Z","timestamp":1759638259681},"reference-count":21,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[2000,3,1]],"date-time":"2000-03-01T00:00:00Z","timestamp":951868800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":4886,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2000,3]]},"DOI":"10.1016\/s0304-3975(99)00192-9","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T01:51:05Z","timestamp":1027648265000},"page":"205-216","source":"Crossref","is-referenced-by-count":12,"title":["Recent results on approximating the Steiner tree problem and its generalizations"],"prefix":"10.1016","volume":"235","author":[{"given":"Vijay V.","family":"Vazirani","sequence":"first","affiliation":[]}],"member":"78","reference":[{"issue":"3","key":"10.1016\/S0304-3975(99)00192-9_BIB1","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1137\/S0097539792236237","article-title":"When trees collide: An approximation algorithm for the generalized Steiner problem on networks","volume":"24","author":"Agrawal","year":"1995","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(99)00192-9_BIB2","doi-asserted-by":"crossref","unstructured":"S. Arora, Nearly linear time approximation schemes for Euclidean TSP and other geometric problems, 38th Ann. Symp. on Foundations of Computer Science, Miami Beach, Florida, 20\u201322 October 1997, IEEE Press, New York, pp. 554\u2013563.","DOI":"10.1109\/SFCS.1997.646145"},{"key":"10.1016\/S0304-3975(99)00192-9_BIB3","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1006\/jagm.1994.1041","article-title":"Improved approximations for the Steiner tree problem","volume":"17","author":"Berman","year":"1994","journal-title":"J. Algorithms"},{"key":"10.1016\/S0304-3975(99)00192-9_BIB4","first-page":"641","article-title":"The k-Steiner ratio in graphs","volume":"000","author":"Borchers","year":"1995","journal-title":"STOC"},{"key":"10.1016\/S0304-3975(99)00192-9_BIB5","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1016\/0196-6774(92)90018-8","article-title":"Random pseudo-polynomial algorithms for exact matroid problems","volume":"13","author":"Camerini","year":"1992","journal-title":"J. Algorithms"},{"key":"10.1016\/S0304-3975(99)00192-9_BIB6","doi-asserted-by":"crossref","first-page":"233","DOI":"10.6028\/jres.071B.032","article-title":"Optimum branchings","volume":"B71","author":"Edmonds","year":"1967","journal-title":"J. Res. Nat. Bur. Standards"},{"key":"10.1016\/S0304-3975(99)00192-9_BIB7","doi-asserted-by":"crossref","unstructured":"N. Garg, V.V. Vazirani, M. Yannakakis, Approximation algorithms for multiway cuts in node-weighted and directed graphs, Proc. 21th Int. Colloq. on Automata, Languages and Programming, 1994.","DOI":"10.1007\/3-540-58201-0_92"},{"key":"10.1016\/S0304-3975(99)00192-9_BIB8","unstructured":"M. Goemans, Personal communication, 1996."},{"issue":"2","key":"10.1016\/S0304-3975(99)00192-9_BIB9","doi-asserted-by":"crossref","first-page":"296","DOI":"10.1137\/S0097539793242618","article-title":"A general approximation technique for constrained forest problems","volume":"24","author":"Goemans","year":"1995","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(99)00192-9_BIB10","first-page":"223","article-title":"Approximation algorithms for network design problems","volume":"000","author":"Goemans","year":"1994","journal-title":"SODA"},{"issue":"2","key":"10.1016\/S0304-3975(99)00192-9_BIB11","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/BF02579273","article-title":"The ellipsoid method and its consequences in combinatorial optimization","volume":"1","author":"Gr\u00f6tschel","year":"1981","journal-title":"Combinatorica"},{"key":"10.1016\/S0304-3975(99)00192-9_BIB12","unstructured":"K. Jain, A factor 2 approximation algorithm for the generalized Steiner network problem, manuscript, 1998."},{"key":"10.1016\/S0304-3975(99)00192-9_BIB13","unstructured":"M. Karpinski, A. Zelikovsky, New approximation algorithms for the Steiner tree problem, Electr. Colloq. Comput. Compl., TR95-030, 1995."},{"key":"10.1016\/S0304-3975(99)00192-9_BIB14","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1007\/BF00288961","article-title":"A fast algorithm for Steiner trees","volume":"15","author":"Kou","year":"1981","journal-title":"Acta Inform."},{"key":"10.1016\/S0304-3975(99)00192-9_BIB15","unstructured":"L. Lovasz, The matroid matching problem, Algebraic Methods in Graph Theory, Colloquia Mathematica Societatis Janos Bolyai, Szeged, Hungary, 1978."},{"key":"10.1016\/S0304-3975(99)00192-9_BIB16","unstructured":"H. Narayanan, H. Saran, V.V. Vazirani, Randomized parallel algorithms for matroid union and intersection, with applications to arborescences and edge-disjoint spanning trees."},{"key":"10.1016\/S0304-3975(99)00192-9_BIB17","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1007\/BF01580444","article-title":"Vertex packing: structural properties and algorithms","volume":"8","author":"Nemhauser","year":"1975","journal-title":"Math. Programm."},{"key":"10.1016\/S0304-3975(99)00192-9_BIB18","doi-asserted-by":"crossref","unstructured":"H.J. Pr\u00f6mel, A. Steger, RNC-approximation algorithms for the Steiner problem, in: R. Reischuk, M. Morvan (Eds.), Proc. Symp. on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, vol. 1200, Springer, Berlin, 1997, pp. 559\u2013570.","DOI":"10.1007\/BFb0023489"},{"key":"10.1016\/S0304-3975(99)00192-9_BIB19","unstructured":"S. Rajagopalan, V.V. Vazirani, On the bidirected cut relaxation for the metric Steiner tree problem, 1998, submitted."},{"key":"10.1016\/S0304-3975(99)00192-9_BIB20","first-page":"15","article-title":"A primal-dual approximation algorithm for generalized Steiner network problems","volume":"000","author":"Williamson","year":"1995","journal-title":"Combinatorica"},{"key":"10.1016\/S0304-3975(99)00192-9_BIB21","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1007\/BF01187035","article-title":"An 11\/6-approximation algorithm for the network Steiner problem","volume":"9","author":"Zelikovsky","year":"1993","journal-title":"Algorithmica"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397599001929?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397599001929?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,2,5]],"date-time":"2020-02-05T00:19:48Z","timestamp":1580861988000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397599001929"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,3]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2000,3]]}},"alternative-id":["S0304397599001929"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(99)00192-9","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2000,3]]}}}