{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T23:24:26Z","timestamp":1770333866218,"version":"3.49.0"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2016,2,18]],"date-time":"2016-02-18T00:00:00Z","timestamp":1455753600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"NWO Veni grant"},{"DOI":"10.13039\/501100002790","name":"Canadian Network for Research and Innovation in Machining Technology, Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002790","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2016,11]]},"DOI":"10.1007\/s10107-016-0987-5","type":"journal-article","created":{"date-parts":[[2016,2,18]],"date-time":"2016-02-18T04:49:56Z","timestamp":1455770996000},"page":"379-406","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree"],"prefix":"10.1007","volume":"160","author":[{"given":"Andreas Emil","family":"Feldmann","sequence":"first","affiliation":[]},{"given":"Jochen","family":"K\u00f6nemann","sequence":"additional","affiliation":[]},{"given":"Neil","family":"Olver","sequence":"additional","affiliation":[]},{"given":"Laura","family":"Sanit\u00e0","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,2,18]]},"reference":[{"issue":"3","key":"987_CR1","doi-asserted-by":"crossref","first-page":"857","DOI":"10.1137\/S0097539795281086","volume":"26","author":"A Borchers","year":"1997","unstructured":"Borchers, A., Du, D.: The $$k$$ k -Steiner ratio in graphs. SIAM J. Comput. 26(3), 857\u2013869 (1997)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"987_CR2","doi-asserted-by":"crossref","first-page":"6:1","DOI":"10.1145\/2432622.2432628","volume":"60","author":"J Byrka","year":"2013","unstructured":"Byrka, J., Grandoni, F., Rothvo\u00df, T., Sanit\u00e0, L.: Steiner tree approximation via iterative randomized rounding. J. ACM 60(1), 6:1\u20136:33 (2013)","journal-title":"J. ACM"},{"key":"987_CR3","doi-asserted-by":"crossref","unstructured":"Chakrabarty, D., K\u00f6nemann, J., Pritchard, D.: Integrality gap of the hypergraphic relaxation of Steiner trees: a short proof of a 1.55 upper bound. Oper. Res. Lett. 38(6), 567\u2013570 (2010)","DOI":"10.1016\/j.orl.2010.09.004"},{"key":"987_CR4","doi-asserted-by":"crossref","unstructured":"Chakrabarty, D., K\u00f6nemann, J., Pritchard, D.: Hypergraphic LP relaxations for Steiner trees. In: International Conference on Integer Programming and Combinatorial Optimization (IPCO), pp. 383\u2013396 (2010)","DOI":"10.1007\/978-3-642-13036-6_29"},{"key":"987_CR5","doi-asserted-by":"crossref","unstructured":"Chleb\u00edk, M., Chleb\u00edkov\u00e1, J.: Approximation hardness ofthe Steiner tree problem on graphs. In: Proceedings, Scandinavian Workshop on Algorithm Theory, pp. 170\u2013179 (2002)","DOI":"10.1007\/3-540-45471-3_18"},{"key":"987_CR6","unstructured":"DIMACS Center for Discrete Mathematics and Theoretical Computer Science. In: 11th DIMACS implementation challenge in collaboration with ICERM: Steiner tree problems. http:\/\/dimacs11.cs.princeton.edu\/ (2014)"},{"key":"987_CR7","doi-asserted-by":"crossref","first-page":"233","DOI":"10.6028\/jres.071B.032","volume":"71B","author":"J Edmonds","year":"1967","unstructured":"Edmonds, J.: Optimum branchings. J. Res. Natl. Bur. Stand. B 71B, 233\u2013240 (1967)","journal-title":"J. Res. Natl. Bur. Stand. B"},{"key":"987_CR8","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF01584082","volume":"1","author":"J Edmonds","year":"1971","unstructured":"Edmonds, J.: Matroids and the greedy algorithm. Math. Program. 1, 127\u2013136 (1971)","journal-title":"Math. Program."},{"key":"987_CR9","unstructured":"Fung, I., Georgiou, K., K\u00f6nemann, J., Sharpe, M.: Efficient algorithms for solving hypergraphic Steiner tree relaxations in quasi-bipartite instances. CoRR, arXiv:1202.5049 (2012)"},{"issue":"1","key":"987_CR10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0116001","volume":"16","author":"EN Gilbert","year":"1968","unstructured":"Gilbert, E.N., Pollak, H.O.: Steiner minimal trees. SIAM J. Appl. Math. 16(1), 1\u201329 (1968)","journal-title":"SIAM J. Appl. Math."},{"issue":"1","key":"987_CR11","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1002\/net.3230230104","volume":"23","author":"MX Goemans","year":"1993","unstructured":"Goemans, M.X., Myung, Y.: A catalog of Steiner tree formulations. Networks 23(1), 19\u201328 (1993)","journal-title":"Networks"},{"key":"987_CR12","doi-asserted-by":"crossref","unstructured":"Goemans, M.X., Olver, N., Rothvo\u00df, T., Zenklusen, R.: Matroids and integrality gaps for hypergraphic steiner tree relaxations. In: Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC), pp. 1161\u201311762 (2012)","DOI":"10.1145\/2213977.2214081"},{"key":"987_CR13","doi-asserted-by":"crossref","unstructured":"Hwang, F.K., Richards, D.S., Winter, P.: The Steiner tree problem. In: Monograph in Annals of Discrete Mathematics, vol. 53. Elsevier, Philadelphia (1992)","DOI":"10.1002\/net.3230220105"},{"key":"987_CR14","doi-asserted-by":"crossref","unstructured":"Jain, K.: A factor 2 approximation algorithm for the generalized Steiner network problem. In: IEEE Symposium on Foundations of Computer Science (FOCS), pp. 448\u2013457 (1998)","DOI":"10.1109\/SFCS.1998.743495"},{"key":"987_CR15","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85\u2013103. Plenum Press, New York (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"1","key":"987_CR16","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1023\/A:1009758919736","volume":"1","author":"M Karpinski","year":"1997","unstructured":"Karpinski, M., Zelikovsky, A.: New approximation algorithms for the Steiner tree problem. J. Comb. Optim. 1(1), 47\u201365 (1997)","journal-title":"J. Comb. Optim."},{"issue":"2","key":"987_CR17","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1007\/s10107-009-0289-2","volume":"127","author":"J K\u00f6nemann","year":"2011","unstructured":"K\u00f6nemann, J., Pritchard, D., Tan, K.: A partition-based relaxation for Steiner trees. Math. Program. 127(2), 345\u2013370 (2011)","journal-title":"Math. Program."},{"issue":"2","key":"987_CR18","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1007\/BF00288961","volume":"15","author":"L Kou","year":"1981","unstructured":"Kou, L., Markowsky, G., Berman, L.: A fast algorithm for Steiner trees. Acta inform. 15(2), 141\u2013145 (1981)","journal-title":"Acta inform."},{"issue":"4","key":"987_CR19","doi-asserted-by":"publisher","first-page":"852","DOI":"10.1145\/2157.322410","volume":"30","author":"N Megiddo","year":"1983","unstructured":"Megiddo, N.: Applying parallel computation algorithms in the design of serial algorithms. J. ACM 30(4), 852\u2013865 (1983). doi: 10.1145\/2157.322410","journal-title":"J. ACM"},{"issue":"3","key":"987_CR20","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/0020-0190(88)90066-X","volume":"27","author":"K Mehlhorn","year":"1988","unstructured":"Mehlhorn, K.: A faster approximation algorithm for the Steiner problem in graphs. Inf. Process. Lett. 27(3), 125\u2013128 (1988)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"987_CR21","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/S0167-6377(02)00185-2","volume":"31","author":"T Polzin","year":"2003","unstructured":"Polzin, T., Vahdati-Daneshmand, S.: On Steiner trees and minimum spanning trees in hypergraphs. Oper. Res. Lett. 31(1), 12\u201320 (2003)","journal-title":"Oper. Res. Lett."},{"key":"987_CR22","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1006\/jagm.2000.1086","volume":"36","author":"HJ Pr\u00f6mel","year":"2000","unstructured":"Pr\u00f6mel, H.J., Steger, A.: A new approximation algorithm for the Steiner tree problem with performance ratio 5\/3. J. Algorithms 36, 89\u2013101 (2000)","journal-title":"J. Algorithms"},{"key":"987_CR23","unstructured":"Rajagopalan, S., Vazirani, V.V.: On the bidirected cut relaxation for the metric Steiner tree problem. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 742\u2013751 (1999)"},{"issue":"1","key":"987_CR24","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1137\/S0895480101393155","volume":"19","author":"G Robins","year":"2005","unstructured":"Robins, G., Zelikovsky, A.: Tighter bounds for graph Steiner tree approximation. SIAM J. Discrete Math. 19(1), 122\u2013134 (2005)","journal-title":"SIAM J. Discrete Math."},{"issue":"6","key":"987_CR25","first-page":"573","volume":"24","author":"H Takahashi","year":"1980","unstructured":"Takahashi, H., Matsuyama, A.: An approximate solution for the Steiner problem in graphs. Math. Jpn. 24(6), 573\u2013577 (1980)","journal-title":"Math. Jpn."},{"key":"987_CR26","volume-title":"Approx. Algorithms","author":"VV Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approx. Algorithms. Springer, Berlin (2001)"},{"key":"987_CR27","unstructured":"Warme, D.: Spanning Trees in Hypergraphs with Applications to Steiner Trees. PhD thesis (1998)"},{"key":"987_CR28","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1007\/3-540-17218-1_46","volume":"246","author":"P Widmayer","year":"1987","unstructured":"Widmayer, P.: On approximation algorithms for Steiner\u2019s problem in graphs. Graph Theor. Concepts Comput. Sci. 246, 17\u201328 (1987)","journal-title":"Graph Theor. Concepts Comput. Sci."},{"key":"987_CR29","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1007\/BF02612335","volume":"28","author":"RT Wong","year":"1984","unstructured":"Wong, R.T.: A dual ascent approach for Steiner tree problems on a directed graph. Math. Program. 28, 271\u2013287 (1984)","journal-title":"Math. Program."},{"issue":"2","key":"987_CR30","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1007\/BF00289500","volume":"23","author":"Y-F Wu","year":"1986","unstructured":"Wu, Y.-F., Widmayer, P., Wong, C.-K.: A faster approximation algorithm for the Steiner problem in graphs. Acta inform. 23(2), 223\u2013229 (1986)","journal-title":"Acta inform."},{"key":"987_CR31","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1007\/BF01187035","volume":"9","author":"A Zelikovsky","year":"1993","unstructured":"Zelikovsky, A.: An $$11\/6$$ 11 \/ 6 -approximation algorithm for the network Steiner problem. Algorithmica 9, 463\u2013470 (1993)","journal-title":"Algorithmica"},{"key":"987_CR32","unstructured":"Zosin, L., Khuller, S.: On directed Steiner trees. In: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 59\u201363, Philadelphia, PA, USA, 2002. Society for Industrial and Applied Mathematics. ISBN 0-89871-513-X. http:\/\/dl.acm.org\/citation.cfm?id=545381.545388"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-016-0987-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-016-0987-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-016-0987-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-016-0987-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,4]],"date-time":"2019-09-04T14:26:12Z","timestamp":1567607172000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-016-0987-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,2,18]]},"references-count":32,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2016,11]]}},"alternative-id":["987"],"URL":"https:\/\/doi.org\/10.1007\/s10107-016-0987-5","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,2,18]]}}}