{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,26]],"date-time":"2026-10-26T18:45:46Z","timestamp":1793040346357,"version":"4.5.0"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2013,2,1]],"date-time":"2013-02-01T00:00:00Z","timestamp":1359676800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["279352"],"award-info":[{"award-number":["279352"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0829878"],"award-info":[{"award-number":["CCF-0829878"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004569","name":"Ministerstwo Nauki i Szkolnictwa Wyzszego","doi-asserted-by":"publisher","award":["N N206 368839"],"award-info":[{"award-number":["N N206 368839"]}],"id":[{"id":"10.13039\/501100004569","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001870","name":"Foundation For Polish Science","doi-asserted-by":"publisher","award":["PLUS\/2010-1\/3"],"award-info":[{"award-number":["PLUS\/2010-1\/3"]}],"id":[{"id":"10.13039\/501100001870","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Feodor Lynen program"},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-11-1-0053"],"award-info":[{"award-number":["N00014-11-1-0053"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100005156","name":"Alexander von Humboldt-Stiftung","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100005156","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2013,2]]},"abstract":"<jats:p>\n                    The Steiner tree problem is one of the most fundamental\n                    <jats:bold>NP<\/jats:bold>\n                    -hard problems: given a weighted undirected graph and a subset of terminal nodes, find a minimum-cost tree spanning the terminals. In a sequence of papers, the approximation ratio for this problem was improved from 2 to 1.55 [Robins and Zelikovsky 2005]. All these algorithms are purely combinatorial. A long-standing open problem is whether there is an LP relaxation of Steiner tree with integrality gap smaller than 2 [Rajagopalan and Vazirani 1999].\n                  <\/jats:p>\n                  <jats:p>\n                    In this article we present an LP-based approximation algorithm for Steiner tree with an improved approximation factor. Our algorithm is based on a, seemingly novel, iterative randomized rounding technique. We consider an LP relaxation of the problem, which is based on the notion of directed components. We sample one component with probability proportional to the value of the associated variable in a fractional solution: the sampled component is contracted and the LP is updated consequently. We iterate this process until all terminals are connected. Our algorithm delivers a solution of cost at most ln(4) +\n                    <jats:italic>\u03b5<\/jats:italic>\n                    &lt; 1.39 times the cost of an optimal Steiner tree. The algorithm can be derandomized using the method of limited independence.\n                  <\/jats:p>\n                  <jats:p>As a by-product of our analysis, we show that the integrality gap of our LP is at most 1.55, hence answering the mentioned open question.<\/jats:p>","DOI":"10.1145\/2432622.2432628","type":"journal-article","created":{"date-parts":[[2013,3,5]],"date-time":"2013-03-05T15:28:36Z","timestamp":1362497316000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":191,"title":["Steiner Tree Approximation via Iterative Randomized Rounding"],"prefix":"10.1145","volume":"60","author":[{"given":"Jaros\u0142aw","family":"Byrka","sequence":"first","affiliation":[{"name":"EPFL and University of Wroc\u0142aw"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fabrizio","family":"Grandoni","sequence":"additional","affiliation":[{"name":"IDSIA, University of Lugano"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"Rothvoss","sequence":"additional","affiliation":[{"name":"EPFL and MIT"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Laura","family":"Sanit\u00e0","sequence":"additional","affiliation":[{"name":"EPFL and University of Waterloo"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2013,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792236237"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Alon N. and Spencer J. 2008. The Probabilistic Method. Wiley.  Alon N. and Spencer J. 2008. The Probabilistic Method . Wiley.","DOI":"10.1002\/9780470277331"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/090771429"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290180"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90039-2"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795281086"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1541885.1541892"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the International Conference on Integer Programming and Combinatorial Optimization (IPCO). 344--358","author":"Chakrabarty D.","unstructured":"Chakrabarty , D. , Devanur , N. R. , and Vazirani , V. V . 2008. New geometry-inspired relaxations and algorithms for the metric Steiner tree problem . In Proceedings of the International Conference on Integer Programming and Combinatorial Optimization (IPCO). 344--358 . Chakrabarty, D., Devanur, N. R., and Vazirani, V. V. 2008. New geometry-inspired relaxations and algorithms for the metric Steiner tree problem. In Proceedings of the International Conference on Integer Programming and Combinatorial Optimization (IPCO). 344--358."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13036-6_29"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2010.09.004"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701398594"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.06.046"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010302"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.6028\/jres.071B.032"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). 928--932","author":"Eisenbrand F.","unstructured":"Eisenbrand , F. and Grandoni , F . 2005. An improved approximation algorithm for virtual private network design . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). 928--932 . Eisenbrand, F. and Grandoni, F. 2005. An improved approximation algorithm for virtual private network design. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). 928--932."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/060654827"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.02.001"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579200"},{"key":"e_1_2_1_20_1","unstructured":"Garey M. R. and Johnson D. S. 1979. Computers and Intractability. W. H. Freeman and Co.  Garey M. R. and Johnson D. S. 1979. Computers and Intractability . W. H. Freeman and Co."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/0116001"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230230104"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793242618"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/11940128_13"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the International Conference on Integer Programming and Combinatorial Optimization (IPCO). 248--260","author":"Grandoni F.","unstructured":"Grandoni , F. and Rothvoss , T . 2011. Approximation algorithms for single and multi-commodity connected facility location . In Proceedings of the International Conference on Integer Programming and Combinatorial Optimization (IPCO). 248--260 . Grandoni, F. and Rothvoss, T. 2011. Approximation algorithms for single and multi-commodity connected facility location. In Proceedings of the International Conference on Integer Programming and Combinatorial Optimization (IPCO). 248--260."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1110.0490"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(01)00335-0"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579273"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380830"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236457.1236458"},{"key":"e_1_2_1_31_1","unstructured":"Hwang F. Richards D. and Winter P. 1992. The Steiner Tree Problem. Monograph in Annals of Discrete Mathematics 53. Elsevier.  Hwang F. Richards D. and Winter P. 1992. The Steiner Tree Problem . Monograph in Annals of Discrete Mathematics 53. Elsevier."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930170004"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2008.12.003"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009758919736"},{"key":"e_1_2_1_35_1","first-page":"191","article-title":"A polynomial algorithm for linear programming","volume":"20","author":"Khachiyan L. G.","year":"1979","unstructured":"Khachiyan , L. G. 1979 . A polynomial algorithm for linear programming . Sov. Math. - Dokl. 20 , 191 -- 194 . (Russian original in Doklady Akademiia Nauk SSSR, 244:1093--1096). Khachiyan, L. G. 1979. A polynomial algorithm for linear programming. Sov. Math. - Dokl. 20, 191--194. (Russian original in Doklady Akademiia Nauk SSSR, 244:1093--1096).","journal-title":"Sov. Math. - Dokl."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/3112661.3112933"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Mitzenmacher M. and Upfal E. 2005. Probability and Computing. Cambridge University Press Cambridge. Randomized algorithms and probabilistic analysis.   Mitzenmacher M. and Upfal E. 2005. Probability and Computing . Cambridge University Press Cambridge. Randomized algorithms and probabilistic analysis.","DOI":"10.1017\/CBO9780511813603"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/11672142_46"},{"key":"e_1_2_1_39_1","unstructured":"Niven I. Zuckerman H. S. and Montgomery H. L. 1991. An Introduction to the Theory of Numbers. John Wiley & Sons Inc.  Niven I. Zuckerman H. S. and Montgomery H. L. 1991. An Introduction to the Theory of Numbers . John Wiley & Sons Inc."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(02)00185-2"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1086"},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). 742--751","author":"Rajagopalan S.","unstructured":"Rajagopalan , S. and Vazirani , V. V . 1999. On the bidirected cut relaxation for the metric Steiner tree problem . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). 742--751 . Rajagopalan, S. and Vazirani, V. V. 1999. On the bidirected cut relaxation for the metric Steiner tree problem. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). 742--751."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(03)00210-2"},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). 770--779","author":"Robins G.","unstructured":"Robins , G. and Zelikovsky , A . 2000. Improved Steiner tree approximation in graphs . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). 770--779 . Robins, G. and Zelikovsky, A. 2000. Improved Steiner tree approximation in graphs. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). 770--779."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480101393155"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1112-3"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.5555\/645591.660077"},{"key":"e_1_2_1_48_1","volume-title":"Approximation Algorithms","author":"Vazirani V. V.","unstructured":"Vazirani , V. V. 2001. Approximation Algorithms . Springer-Verlag . Vazirani, V. V. 2001. Approximation Algorithms. Springer-Verlag."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01187035"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2432622.2432628","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2432622.2432628","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:18:20Z","timestamp":1750220300000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2432622.2432628"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,2]]},"references-count":49,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,2]]}},"alternative-id":["10.1145\/2432622.2432628"],"URL":"https:\/\/doi.org\/10.1145\/2432622.2432628","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,2]]},"assertion":[{"value":"2010-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-02-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}