{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:29:05Z","timestamp":1750220945412,"version":"3.41.0"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2019,1,30]],"date-time":"2019-01-30T00:00:00Z","timestamp":1548806400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"German Research Foundation","doi-asserted-by":"crossref","award":["CH 897\/1-1 and CH 897\/3-1"],"award-info":[{"award-number":["CH 897\/1-1 and CH 897\/3-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2019,12,17]]},"abstract":"<jats:p>\n            In this experimental study, we consider Steiner tree approximation algorithms that guarantee a constant approximation ratio smaller than 2. The considered greedy algorithms and approaches based on linear programming involve the incorporation of\n            <jats:italic>k<\/jats:italic>\n            -restricted full components for some\n            <jats:italic>k<\/jats:italic>\n            \u2265 3. For most of the algorithms, their strongest theoretical approximation bounds are only achieved for\n            <jats:italic>k<\/jats:italic>\n            \u2192 \u221e. However, the running time is also exponentially dependent on\n            <jats:italic>k<\/jats:italic>\n            , so only small\n            <jats:italic>k<\/jats:italic>\n            are tractable in practice.\n          <\/jats:p>\n          <jats:p>We investigate different implementation aspects and parameter choices that finally allow us to construct algorithms (somewhat) feasible for practical use. We compare the algorithms against each other, to an exact algorithm based on integer linear programs, and to fast and simple 2-approximations as well as state-of-the-art heuristics.<\/jats:p>","DOI":"10.1145\/3299903","type":"journal-article","created":{"date-parts":[[2019,1,30]],"date-time":"2019-01-30T12:58:34Z","timestamp":1548853114000},"page":"1-33","source":"Crossref","is-referenced-by-count":6,"title":["Strong Steiner Tree Approximations in Practice"],"prefix":"10.1145","volume":"24","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5274-0447","authenticated-orcid":false,"given":"Stephan","family":"Beyer","sequence":"first","affiliation":[{"name":"Osnabr\u00fcck University, Wachsbleiche, Osnabr\u00fcck, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4681-5550","authenticated-orcid":false,"given":"Markus","family":"Chimani","sequence":"additional","affiliation":[{"name":"Osnabr\u00fcck University, Wachsbleiche, Osnabr\u00fcck, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,1,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230100207"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/646388.690192"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1041"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90039-2"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS\u201914)","volume":"8934","author":"Beyer S.","unstructured":"S. Beyer and M. Chimani . 2014. Steiner tree 1.39-approximation in practice . In Proceedings of the Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS\u201914) (LNCS), Vol. 8934 . 60--72. S. Beyer and M. Chimani. 2014. Steiner tree 1.39-approximation in practice. In Proceedings of the Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS\u201914) (LNCS), Vol. 8934. 60--72."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-26626-8_44"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225282"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2432622.2432628"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13036-6_29"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2010.09.004"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2012.04.016"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25591-5_6"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.06.046"},{"volume-title":"Proceedings of the 11th DIMACS Challenge.","author":"Ciebiera K.","key":"e_1_2_1_14_1","unstructured":"K. Ciebiera , P. Godlewski , P. Sankowski , and P. Wygocki . 2014. Approximation algorithms for Steiner tree problems based on universal solution frameworks . In Proceedings of the 11th DIMACS Challenge. Retrieved from http:\/\/arxiv.org\/abs\/1410.7534. K. Ciebiera, P. Godlewski, P. Sankowski, and P. Wygocki. 2014. Approximation algorithms for Steiner tree problems based on universal solution frameworks. In Proceedings of the 11th DIMACS Challenge. Retrieved from http:\/\/arxiv.org\/abs\/1410.7534."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_16_1","unstructured":"DIMACS. 2014. 11th DIMACS Challenge. http:\/\/dimacs11.zib.de.  DIMACS. 2014. 11th DIMACS Challenge. http:\/\/dimacs11.zib.de."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010302"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230190506"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/2783147.2783151"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the International Symposium on Parameterized and Exact Computation (IPEC\u201913)","volume":"8246","author":"Fafianie S.","unstructured":"S. Fafianie , H. L. Bodlaender , and J. Nederlof . 2013. Speeding up dynamic programming with representative sets\u2014An experimental evaluation of algorithms for Steiner tree on tree decompositions . In Proceedings of the International Symposium on Parameterized and Exact Computation (IPEC\u201913) (LNCS), Vol. 8246 . 321--334. S. Fafianie, H. L. Bodlaender, and J. Nederlof. 2013. Speeding up dynamic programming with representative sets\u2014An experimental evaluation of algorithms for Steiner tree on tree decompositions. In Proceedings of the International Symposium on Parameterized and Exact Computation (IPEC\u201913) (LNCS), Vol. 8246. 321--334."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-016-0111-0"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/367766.368168"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/0116001"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214081"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793242618"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"C. Gr\u00f6pl S. Hougardy T. Nierhoff and H. J. Pr\u00f6mel. 2001. Approximation algorithms for the Steiner tree problem in graphs. In Steiner Trees in Industry (Combinatorial Optimization). 235--279.  C. Gr\u00f6pl S. Hougardy T. Nierhoff and H. J. Pr\u00f6mel. 2001. Approximation algorithms for the Steiner tree problem in graphs. In Steiner Trees in Industry (Combinatorial Optimization). 235--279.","DOI":"10.1007\/978-1-4613-0255-1_7"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2396761.2398460"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213024"},{"volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201999)","author":"Hougardy S.","key":"e_1_2_1_30_1","unstructured":"S. Hougardy and H. J. Pr\u00f6mel . 1999. A 1.598 approximation algorithm for the Steiner problem in graphs . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201999) . ACM\/SIAM, 448--453. S. Hougardy and H. J. Pr\u00f6mel. 1999. A 1.598 approximation algorithm for the Steiner problem in graphs. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201999). ACM\/SIAM, 448--453."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-016-0110-1"},{"key":"e_1_2_1_32_1","article-title":"The Steiner Tree Problem","volume":"51","author":"Hwang F. K.","year":"1992","unstructured":"F. K. Hwang , D. S. Richards , and P. Winter . 1992 . The Steiner Tree Problem . Annals of Discrete Mathematics , Vol. 51. Elsevier Science. F. K. Hwang, D. S. Richards, and P. Winter. 1992. The Steiner Tree Problem. Annals of Discrete Mathematics, Vol. 51. Elsevier Science.","journal-title":"Annals of Discrete Mathematics"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.144853"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_2_1_35_1","unstructured":"M. Karpinski and A. Zelikovsky. 1995. 1.757 and 1.267\u2014Approximation algorithms for the network and rectilinear Steiner tree problems. ECCC 2 3 (1995).  M. Karpinski and A. Zelikovsky. 1995. 1.757 and 1.267\u2014Approximation algorithms for the network and rectilinear Steiner tree problems. ECCC 2 3 (1995)."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0037(199810)32:3<207::AID-NET5>3.0.CO;2-O"},{"key":"e_1_2_1_37_1","unstructured":"T. Koch A. Martin and S. Vo\u00df. 2000. SteinLib: An Updated Library on Steiner Tree Problems in Graphs. Technical Report ZIB-Report 00-37. Konrad-Zuse-Zentrum f\u00fcr Informationstechnik Berlin. Retrieved from http:\/\/elib.zib.de\/steinlib.  T. Koch A. Martin and S. Vo\u00df. 2000. SteinLib: An Updated Library on Steiner Tree Problems in Graphs. Technical Report ZIB-Report 00-37. Konrad-Zuse-Zentrum f\u00fcr Informationstechnik Berlin. Retrieved from http:\/\/elib.zib.de\/steinlib."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/3112661.3112933"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288961"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of Hybrid Metaheuristics 2014 (LNCS)","volume":"8457","author":"Leitner M.","unstructured":"M. Leitner , I. Ljubic , M. Luipersbeck , and M. Resch . 2014. A partition-based heuristic for the Steiner tree problem in large graphs . In Proceedings of Hybrid Metaheuristics 2014 (LNCS) , Vol. 8457 . 56--70. M. Leitner, I. Ljubic, M. Luipersbeck, and M. Resch. 2014. A partition-based heuristic for the Steiner tree problem in large graphs. In Proceedings of Hybrid Metaheuristics 2014 (LNCS), Vol. 8457. 56--70."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90066-X"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-017-0123-4"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62233"},{"volume-title":"Proceedings of the Metaheuristics International Conference (MIC\u201901)","author":"de Arag\u00e3o M. Poggi","key":"e_1_2_1_44_1","unstructured":"M. Poggi de Arag\u00e3o , C. C. Ribeiro , E. Uchoa , and R. F. Werneck . 2001. Hybrid local search for the Steiner problem in graphs . In Proceedings of the Metaheuristics International Conference (MIC\u201901) . 429--433. M. Poggi de Arag\u00e3o, C. C. Ribeiro, E. Uchoa, and R. F. Werneck. 2001. Hybrid local search for the Steiner problem in graphs. In Proceedings of the Metaheuristics International Conference (MIC\u201901). 429--433."},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX\u201902)","volume":"2409","author":"de Arag\u00e3o M. Poggi","unstructured":"M. Poggi de Arag\u00e3o and R. F. Werneck . 2002. On the implementation of MST-based heuristics for the Steiner problem in graphs . In Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX\u201902) (LNCS), Vol. 2409 . 1--15. M. Poggi de Arag\u00e3o and R. F. Werneck. 2002. On the implementation of MST-based heuristics for the Steiner problem in graphs. In Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX\u201902) (LNCS), Vol. 2409. 1--15."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(00)00319-X"},{"key":"e_1_2_1_48_1","volume-title":"Proceedings of the European Symposium on Algorithms (ESA\u201902)","volume":"2461","author":"Polzin T.","unstructured":"T. Polzin and S. Vahdati Daneshmand . 2002. Extending reduction techniques for the Steiner tree problem . In Proceedings of the European Symposium on Algorithms (ESA\u201902) (LNCS), Vol. 2461 . 795--807. T. Polzin and S. Vahdati Daneshmand. 2002. Extending reduction techniques for the Steiner tree problem. In Proceedings of the European Symposium on Algorithms (ESA\u201902) (LNCS), Vol. 2461. 795--807."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(02)00185-2"},{"key":"e_1_2_1_50_1","volume-title":"Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS\u201997)","volume":"1200","author":"Pr\u00f6mel H. J.","unstructured":"H. J. Pr\u00f6mel and A. Steger . 1997. RNC-approximation algorithms for the Steiner problem . In Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS\u201997) (LNCS), Vol. 1200 . 559--570. H. J. Pr\u00f6mel and A. Steger. 1997. RNC-approximation algorithms for the Steiner problem. In Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS\u201997) (LNCS), Vol. 1200. 559--570."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1080\/0020739830140103"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480101393155"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230120309"},{"key":"e_1_2_1_54_1","first-page":"573","article-title":"An approximate solution for the Steiner problem in graphs","volume":"24","author":"Takahashi H.","year":"1980","unstructured":"H. Takahashi and A. Matsuyama . 1980 . An approximate solution for the Steiner problem in graphs . Math. Japon. 24 (1980), 573 -- 577 . H. Takahashi and A. Matsuyama. 1980. An approximate solution for the Steiner problem in graphs. Math. Japon. 24 (1980), 573--577.","journal-title":"Math. Japon."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.08.005"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02612335"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70655-1"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90201-J"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01187035"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3299903","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3299903","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:53:39Z","timestamp":1750204419000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3299903"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1,30]]},"references-count":57,"alternative-id":["10.1145\/3299903"],"URL":"https:\/\/doi.org\/10.1145\/3299903","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2019,1,30]]}}}