{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T23:49:41Z","timestamp":1773964181639,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":42,"publisher":"ACM","license":[{"start":{"date-parts":[[2010,6,5]],"date-time":"2010-06-05T00:00:00Z","timestamp":1275696000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2010,6,5]]},"DOI":"10.1145\/1806689.1806769","type":"proceedings-article","created":{"date-parts":[[2010,6,8]],"date-time":"2010-06-08T12:37:34Z","timestamp":1276000654000},"page":"583-592","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":173,"title":["An improved LP-based approximation for steiner tree"],"prefix":"10.1145","author":[{"given":"Jaroslaw","family":"Byrka","sequence":"first","affiliation":[{"name":"EPFL, Lausanne, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fabrizio","family":"Grandoni","sequence":"additional","affiliation":[{"name":"Universita di Roma Tor Vergata, Rome, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Rothvo\u00df","sequence":"additional","affiliation":[{"name":"EPFL, Lausanne, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Laura","family":"Sanit\u00e0","sequence":"additional","affiliation":[{"name":"EPFL, Lausanne, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,6,5]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792236237"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"crossref","DOI":"10.1002\/9780470277331","volume-title":"The probabilistic method","author":"Alon N.","year":"2008","unstructured":"N. Alon and J. Spencer . The probabilistic method . Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons Inc ., Hoboken, NJ, third edition, 2008 . N. Alon and J. Spencer. The probabilistic method. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons Inc., Hoboken, NJ, third edition, 2008."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.39"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290180"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90039-2"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795281086"},{"key":"e_1_3_2_1_7_1","first-page":"1285","volume-title":"SODA","author":"Borradaile G.","year":"2007","unstructured":"G. Borradaile , C. Kenyon-Mathieu , and P. Klein . A polynomial-time approximation scheme for Steiner tree in planar graphs . In SODA , pages 1285 -- 1294 , 2007 . G. Borradaile, C. Kenyon-Mathieu, and P. Klein. A polynomial-time approximation scheme for Steiner tree in planar graphs. In SODA, pages 1285--1294, 2007."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1788814.1788846"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701398594"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.06.046"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010302"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.6028\/jres.071B.032"},{"key":"e_1_3_2_1_13_1","first-page":"928","volume-title":"SODA","author":"Eisenbrand F.","year":"2005","unstructured":"F. Eisenbrand and F. Grandoni . An improved approximation algorithm for virtual private network design . In SODA , pages 928 -- 932 , 2005 . F. Eisenbrand and F. Grandoni. An improved approximation algorithm for virtual private network design. In SODA, pages 928--932, 2005."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/060654827"},{"key":"e_1_3_2_1_15_1","first-page":"1174","volume-title":"SODA","author":"Eisenbrand F.","year":"2008","unstructured":"F. Eisenbrand , F. Grandoni , T. Rothvo\u00df , and G. Sch\u00e4fer . Approximating connected facility location problems via random facility sampling and core detouring . In SODA , pages 1174 -- 1183 , 2008 . F. Eisenbrand, F. Grandoni, T. Rothvo\u00df, and G. Sch\u00e4fer. Approximating connected facility location problems via random facility sampling and core detouring. In SODA, pages 1174--1183, 2008."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.02.001"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579200"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/0132071"},{"key":"e_1_3_2_1_19_1","volume-title":"Computers and intractability","author":"Garey M. R.","year":"1979","unstructured":"M. R. Garey and D. S. Johnson . Computers and intractability . W. H. Freeman and Co., San Francisco , Calif., 1979 . A guide to the theory of NP-completeness, A Series of Books in the Mathematical Sciences. M. R. Garey and D. S. Johnson. Computers and intractability. W. H. Freeman and Co., San Francisco, Calif., 1979. A guide to the theory of NP-completeness, A Series of Books in the Mathematical Sciences."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/0116001"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230230104"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793242618"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/11940128_13"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579273"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380830"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236457.1236458"},{"key":"e_1_3_2_1_27_1","volume-title":"The Steiner tree problem. Monograph in Annals of Discrete Mathematics, 53","author":"Hwang F.K.","year":"1992","unstructured":"F.K. Hwang , D.S. Richards , and P. Winter . The Steiner tree problem. Monograph in Annals of Discrete Mathematics, 53 . Elsevier , Amsterdam , 1992 . F.K. Hwang, D.S. Richards, and P. Winter. The Steiner tree problem. Monograph in Annals of Discrete Mathematics, 53. Elsevier, Amsterdam, 1992."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/795664.796444"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009758919736"},{"key":"e_1_3_2_1_30_1","first-page":"191","article-title":"A polynomial algorithm for linear programming","volume":"20","author":"Khachiyan L. G.","year":"1979","unstructured":"L. G. Khachiyan . A polynomial algorithm for linear programming . Soviet Math. Doklady , 20 : 191 -- 194 , 1979 . (Russian original in Doklady Akademiia Nauk SSSR, 244:1093--1096). L. G. Khachiyan. A polynomial algorithm for linear programming. Soviet Math. Doklady, 20:191--194, 1979. (Russian original in Doklady Akademiia Nauk SSSR, 244:1093--1096).","journal-title":"Soviet Math. Doklady"},{"key":"e_1_3_2_1_31_1","volume-title":"A partition-based relaxation for Steiner trees. CoRR, abs\/0712.3568","author":"K\u00f6nemann J.","year":"2007","unstructured":"J. K\u00f6nemann , D. Pritchard , and K. Tan . A partition-based relaxation for Steiner trees. CoRR, abs\/0712.3568 , 2007 . J. K\u00f6nemann, D. Pritchard, and K. Tan. A partition-based relaxation for Steiner trees. CoRR, abs\/0712.3568, 2007."},{"key":"e_1_3_2_1_32_1","volume-title":"Combinatorial Optimization -- Theory and Algorithms","author":"Korte B.","year":"2002","unstructured":"B. Korte and J. Vygen . Combinatorial Optimization -- Theory and Algorithms . Springer-Verlag , Second Edition , 2002 . B. Korte and J. Vygen. Combinatorial Optimization -- Theory and Algorithms. Springer-Verlag, Second Edition, 2002."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/11672142_46"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(02)00185-2"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1086"},{"key":"e_1_3_2_1_36_1","first-page":"742","volume-title":"SODA","author":"Rajagopalan S.","year":"1999","unstructured":"S. Rajagopalan and V. V. Vazirani . On the bidirected cut relaxation for the metric Steiner tree problem . In SODA , pages 742 -- 751 , 1999 . S. Rajagopalan and V. V. Vazirani. On the bidirected cut relaxation for the metric Steiner tree problem. In SODA, pages 742--751, 1999."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(03)00210-2"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480101393155"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1112-3"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/645591.660077"},{"key":"e_1_3_2_1_41_1","volume-title":"Approximation Algorithms","author":"Vazirani V. V.","year":"2001","unstructured":"V. V. Vazirani . Approximation Algorithms . Springer-Verlag , 2001 . V. V. Vazirani. Approximation Algorithms. Springer-Verlag, 2001."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"crossref","unstructured":"A. Z. Zelikovsky. An 11\/6-approximation algorithm for the network Steiner problem. Algorithmica 9:463--470 1993.  A. Z. Zelikovsky. An 11\/6-approximation algorithm for the network Steiner problem. Algorithmica 9:463--470 1993.","DOI":"10.1007\/BF01187035"}],"event":{"name":"STOC'10: Symposium on Theory of Computing","location":"Cambridge Massachusetts USA","acronym":"STOC'10","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the forty-second ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1806689.1806769","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1806689.1806769","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:39:37Z","timestamp":1750246777000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1806689.1806769"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,6,5]]},"references-count":42,"alternative-id":["10.1145\/1806689.1806769","10.1145\/1806689"],"URL":"https:\/\/doi.org\/10.1145\/1806689.1806769","relation":{},"subject":[],"published":{"date-parts":[[2010,6,5]]},"assertion":[{"value":"2010-06-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}