{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:46:49Z","timestamp":1781077609857,"version":"3.54.1"},"publisher-location":"Cham","reference-count":41,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031931116","type":"print"},{"value":"9783031931123","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-93112-3_9","type":"book-chapter","created":{"date-parts":[[2025,6,10]],"date-time":"2025-06-10T04:56:01Z","timestamp":1749531361000},"page":"114-127","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On the\u00a0Bidirected Cut Relaxation for\u00a0Steiner Forest"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3387-0913","authenticated-orcid":false,"given":"Jaros\u0142aw","family":"Byrka","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9676-4931","authenticated-orcid":false,"given":"Fabrizio","family":"Grandoni","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9749-2600","authenticated-orcid":false,"given":"Vera","family":"Traub","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,6,4]]},"reference":[{"issue":"3","key":"9_CR1","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1137\/S0097539792236237","volume":"24","author":"A Agrawal","year":"1995","unstructured":"Agrawal, A., Klein, P.N., Ravi, R.: When trees collide: an approximation algorithm for the generalized Steiner problem on networks. SIAM J. Comput. 24(3), 440\u2013456 (1995). https:\/\/doi.org\/10.1137\/S0097539792236237","journal-title":"SIAM J. Comput."},{"key":"9_CR2","doi-asserted-by":"publisher","unstructured":"Ahmadi, A., Gholami, I., Hajiaghayi, M., Jabbarzade, P., Mahdavi, M.: 2-approximation for prize-collecting Steiner forest. In: Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 669\u2013693 (2024). https:\/\/doi.org\/10.1137\/1.9781611977912.25","DOI":"10.1137\/1.9781611977912.25"},{"key":"9_CR3","doi-asserted-by":"publisher","unstructured":"Ahmadi, A., Gholami, I., Hajiaghayi, M., Jabbarzade, P., Mahdavi, M.: Prize-collecting Steiner tree: A 1.79 approximation. In: Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC), pp. 1641\u20131652 (2024). https:\/\/doi.org\/10.1145\/3618260.3649789","DOI":"10.1145\/3618260.3649789"},{"key":"9_CR4","doi-asserted-by":"publisher","unstructured":"Bateni, M., Hajiaghayi, M., Marx, D.: Approximation schemes for Steiner forest on planar graphs and graphs of bounded treewidth. J. ACM 58(5) (2011). https:\/\/doi.org\/10.1145\/2027216.2027219","DOI":"10.1145\/2027216.2027219"},{"key":"9_CR5","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/j.ic.2012.10.007","volume":"222","author":"P Berman","year":"2013","unstructured":"Berman, P., Bhattacharyya, A., Makarychev, K., Raskhodnikova, S., Yaroslavtsev, G.: Approximation algorithms for spanner problems and directed Steiner forest. Inf. Comput. 222, 93\u2013107 (2013)","journal-title":"Inf. Comput."},{"issue":"3","key":"9_CR6","first-page":"1","volume":"11","author":"G Borradaile","year":"2015","unstructured":"Borradaile, G., Klein, P.N., Mathieu, C.: A polynomial-time approximation scheme for Euclidean Steiner forest. ACM Trans. Algorithms (TALG) 11(3), 1\u201320 (2015)","journal-title":"ACM Trans. Algorithms (TALG)"},{"issue":"3","key":"9_CR7","doi-asserted-by":"publisher","first-page":"1730","DOI":"10.1137\/20M1372822","volume":"36","author":"S Boyd","year":"2022","unstructured":"Boyd, S., et al.: A 4\/3-approximation algorithm for the minimum 2-edge connected multisubgraph problem in the half-integral case. SIAM J. Discret. Math. 36(3), 1730\u20131747 (2022)","journal-title":"SIAM J. Discret. Math."},{"issue":"3","key":"9_CR8","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1137\/21M1421143","volume":"52","author":"J Byrka","year":"2023","unstructured":"Byrka, J., Grandoni, F., Ameli, A.J.: Breaching the 2-approximation barrier for connectivity augmentation: a reduction to Steiner tree. SIAM J. Comput. 52(3), 718\u2013739 (2023). https:\/\/doi.org\/10.1137\/21M1421143","journal-title":"SIAM J. Comput."},{"key":"9_CR9","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1145\/2432622.2432628","DOI":"10.1145\/2432622.2432628"},{"key":"9_CR10","doi-asserted-by":"crossref","unstructured":"Byrka, J., Grandoni, F., Traub, V.: The bidirected cut relaxation for Steiner tree has integrality gap smaller than 2. In: Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science (FOCS) (2024)","DOI":"10.1109\/FOCS61266.2024.00052"},{"key":"9_CR11","doi-asserted-by":"publisher","unstructured":"Byrka, J., Grandoni, F., Traub, V.: On the bidirected cut relaxation for Steiner forest. CoRR abs\/2412.06518 (2024). https:\/\/doi.org\/10.48550\/ARXIV.2412.06518","DOI":"10.48550\/ARXIV.2412.06518"},{"key":"9_CR12","doi-asserted-by":"crossref","unstructured":"Carr, R., Ravi, R.: A new bound for the 2-edge connected subgraph problem. In: International Conference on Integer Programming and Combinatorial Optimization, pp. 112\u2013125. Springer, Cham (1998)","DOI":"10.1007\/3-540-69346-7_9"},{"key":"9_CR13","doi-asserted-by":"publisher","unstructured":"Cecchetto, F., Traub, V., Zenklusen, R.: Bridging the gap between tree and connectivity augmentation: unified and stronger approaches. In: Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC), pp. 370\u2013383 (2021). https:\/\/doi.org\/10.1145\/3406325.3451086","DOI":"10.1145\/3406325.3451086"},{"issue":"1","key":"9_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/S10107-009-0299-0","volume":"130","author":"D Chakrabarty","year":"2011","unstructured":"Chakrabarty, D., Devanur, N.R., Vazirani, V.V.: New geometry-inspired relaxations and algorithms for the metric Steiner tree problem. Math. Program. 130(1), 1\u201332 (2011). https:\/\/doi.org\/10.1007\/S10107-009-0299-0","journal-title":"Math. Program."},{"key":"9_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1007\/978-3-642-13036-6_29","volume-title":"Integer Programming and Combinatorial Optimization","author":"D Chakrabarty","year":"2010","unstructured":"Chakrabarty, D., K\u00f6nemann, J., Pritchard, D.: Hypergraphic LP relaxations for Steiner trees. In: Eisenbrand, F., Shepherd, F.B. (eds.) IPCO 2010. LNCS, vol. 6080, pp. 383\u2013396. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-13036-6_29"},{"issue":"1","key":"9_CR16","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1006\/jagm.1999.1042","volume":"33","author":"M Charikar","year":"1999","unstructured":"Charikar, M., et al.: Approximation algorithms for directed Steiner problems. J. Algorithms 33(1), 73\u201391 (1999). https:\/\/doi.org\/10.1006\/jagm.1999.1042","journal-title":"J. Algorithms"},{"issue":"2","key":"9_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1921659.1921664","volume":"7","author":"C Chekuri","year":"2011","unstructured":"Chekuri, C., Even, G., Gupta, A., Segev, D.: Set connectivity problems in undirected graphs and the directed Steiner network problem. ACM Trans. Algorithms (TALG) 7(2), 1\u201317 (2011)","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"9_CR18","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Jain, R.: A polylogarithmic approximation for directed Steiner forest in planar digraphs. arXiv preprint arXiv:2410.17403 (2024)","DOI":"10.1137\/1.9781611978322.67"},{"issue":"3","key":"9_CR19","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/J.TCS.2008.06.046","volume":"406","author":"M Chleb\u00edk","year":"2008","unstructured":"Chleb\u00edk, M., Chleb\u00edkov\u00e1, J.: The Steiner tree problem on graphs: inapproximability results. Theor. Comput. Sci. 406(3), 207\u2013214 (2008). https:\/\/doi.org\/10.1016\/J.TCS.2008.06.046","journal-title":"Theor. Comput. Sci."},{"key":"9_CR20","doi-asserted-by":"publisher","first-page":"233","DOI":"10.6028\/jres.071B.032","volume":"B71","author":"J Edmonds","year":"1967","unstructured":"Edmonds, J.: Optimum branchings. J. Res. Natl. Bur. Stand. B71, 233\u2013240 (1967)","journal-title":"J. Res. Natl. Bur. Stand."},{"issue":"1\u20132","key":"9_CR21","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/S10107-016-0987-5","volume":"160","author":"AE Feldmann","year":"2016","unstructured":"Feldmann, A.E., K\u00f6nemann, J., Olver, N., Sanit\u00e0, L.: On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree. Math. Program. 160(1\u20132), 379\u2013406 (2016). https:\/\/doi.org\/10.1007\/S10107-016-0987-5","journal-title":"Math. Program."},{"issue":"1","key":"9_CR22","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1002\/NET.3230230104","journal-title":"Networks"},{"key":"9_CR23","doi-asserted-by":"publisher","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 ACM Symposium on Theory of Computing Conference (STOC), pp. 1161\u20131176 (2012). https:\/\/doi.org\/10.1145\/2213977.2214081","DOI":"10.1145\/2213977.2214081"},{"issue":"2","key":"9_CR24","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1137\/S0097539793242618","volume":"24","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: A general approximation technique for constrained forest problems. SIAM J. Comput. 24(2), 296\u2013317 (1995). https:\/\/doi.org\/10.1137\/S0097539793242618","journal-title":"SIAM J. Comput."},{"key":"9_CR25","doi-asserted-by":"publisher","unstructured":"Grandoni, F., Ameli, A.J., Traub, V.: Breaching the 2-approximation barrier for the forest augmentation problem. In: Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC), pp. 1598\u20131611 (2022). https:\/\/doi.org\/10.1145\/3519935.3520035","DOI":"10.1145\/3519935.3520035"},{"key":"9_CR26","doi-asserted-by":"publisher","unstructured":"Grandoni, F., Laekhanukit, B., Li, S.: O(log$$ ^{2}$$k\/log log k)-approximation algorithm for directed Steiner tree: a tight quasi-polynomial-time algorithm. In: Proceedings of the 51st Annual ACM Symposium on Theory of Computing (STOC), pp. 253\u2013264 (2019). https:\/\/doi.org\/10.1145\/3313276.3316349","DOI":"10.1145\/3313276.3316349"},{"key":"9_CR27","unstructured":"Hyatt-Denesik, D., Jabal\u00a0Ameli, A., Sanit\u00e0, L.: Finding almost tight witness trees. In: 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), pp. 79:1\u201379:16 (2023)"},{"issue":"1","key":"9_CR28","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/S004930170004","volume":"21","author":"K Jain","year":"2001","unstructured":"Jain, K.: A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica 21(1), 39\u201360 (2001). https:\/\/doi.org\/10.1007\/S004930170004","journal-title":"Combinatorica"},{"key":"9_CR29","doi-asserted-by":"publisher","unstructured":"Karlin, A.R., Klein, N., Oveis\u00a0Gharan, S.: An improved approximation algorithm for TSP in the half integral case. In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, pp. 28\u201339. Association for Computing Machinery, New York (2020). https:\/\/doi.org\/10.1145\/3357713.3384273","DOI":"10.1145\/3357713.3384273"},{"key":"9_CR30","unstructured":"Karpinski, M., Lewandowski, M., Meesum, S.M., Mnich, M.: Dense Steiner problems: approximation algorithms and inapproximability. CoRR abs\/2004.14102 (2020). https:\/\/arxiv.org\/abs\/2004.14102"},{"issue":"1","key":"9_CR31","doi-asserted-by":"publisher","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 problems. J. Comb. Optim. 1(1), 47\u201365 (1997). https:\/\/doi.org\/10.1023\/A:1009758919736","journal-title":"J. Comb. Optim."},{"issue":"1","key":"9_CR32","doi-asserted-by":"publisher","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(1), 89\u2013101 (2000). https:\/\/doi.org\/10.1006\/JAGM.2000.1086","journal-title":"J. Algorithms"},{"issue":"1","key":"9_CR33","doi-asserted-by":"publisher","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. Discret. Math. 19(1), 122\u2013134 (2005). https:\/\/doi.org\/10.1137\/S0895480101393155","journal-title":"SIAM J. Discret. Math."},{"issue":"1","key":"9_CR34","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/S10107-019-01460-6","volume":"186","author":"DR Schmidt","year":"2021","unstructured":"Schmidt, D.R., Zey, B., Margot, F.: Stronger MIP formulations for the Steiner forest problem. Math. Program. 186(1), 373\u2013407 (2021). https:\/\/doi.org\/10.1007\/S10107-019-01460-6","journal-title":"Math. Program."},{"key":"9_CR35","doi-asserted-by":"publisher","unstructured":"Traub, V., Zenklusen, R.: A better-than-2 approximation for weighted tree augmentation. In: Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 1\u201312 (2021). https:\/\/doi.org\/10.1109\/FOCS52979.2021.00010","DOI":"10.1109\/FOCS52979.2021.00010"},{"key":"9_CR36","doi-asserted-by":"publisher","unstructured":"Traub, V., Zenklusen, R.: Local search for weighted tree augmentation and Steiner tree. In: Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 3253\u20133272 (2022). https:\/\/doi.org\/10.1137\/1.9781611977073.128","DOI":"10.1137\/1.9781611977073.128"},{"key":"9_CR37","doi-asserted-by":"publisher","unstructured":"Traub, V., Zenklusen, R.: A (1.5+$$\\epsilon $$)-approximation algorithm for weighted connectivity augmentation. In: Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC), pp. 1820\u20131833 (2023). https:\/\/doi.org\/10.1145\/3564246.3585122","DOI":"10.1145\/3564246.3585122"},{"key":"9_CR38","unstructured":"Vicari, R.: Simplex based Steiner tree instances yield large integrality gaps for the bidirected cut relaxation. CoRR abs\/2002.07912 (2020). https:\/\/arxiv.org\/abs\/2002.07912"},{"key":"9_CR39","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511921735","volume-title":"The Design of Approximation Algorithms","author":"DP Williamson","year":"2011","unstructured":"Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms. Cambridge University Press, Cambridge (2011)"},{"key":"9_CR40","unstructured":"Zelikovsky, A.: Better approximation bounds for the network and Euclidean Steiner tree problems. Technical report, University of Virginia, cS-96-06 (1996)"},{"issue":"5","key":"9_CR41","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/BF01187035","volume":"9","author":"A Zelikovsky","year":"1993","unstructured":"Zelikovsky, A.: An 11\/6-approximation algorithm for the network Steiner problem. Algorithmica 9(5), 463\u2013470 (1993). https:\/\/doi.org\/10.1007\/BF01187035","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-93112-3_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T10:53:12Z","timestamp":1760007192000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-93112-3_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031931116","9783031931123"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-93112-3_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"4 June 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IPCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Integer Programming and Combinatorial Optimization","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Baltimore, MD","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 June 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 June 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ipco2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/ipco25.cs.jhu.edu\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}