{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,8]],"date-time":"2026-03-08T08:33:59Z","timestamp":1772958839941,"version":"3.50.1"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2014,10,30]],"date-time":"2014-10-30T00:00:00Z","timestamp":1414627200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["No. OGP0138432 and No. 28833"],"award-info":[{"award-number":["No. OGP0138432 and No. 28833"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2014,11,17]]},"abstract":"<jats:p>\n            The Directed Steiner Tree (DST) problem is a cornerstone problem in network design. We focus on the generalization of the problem with higher connectivity requirements. The problem with one root and two sinks is APX-hard. The problem with one root and many sinks is as hard to approximate as the directed Steiner forest problem, and the latter is well known to be as hard to approximate as the label cover problem. Utilizing previous techniques, we strengthen these results and extend them to undirected graphs. Specifically, we give an \u03a9(\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>\u03f5<\/jats:sup>\n            ) hardness bound for the rooted\n            <jats:italic>k<\/jats:italic>\n            -connectivity problem in undirected graphs. As a consequence, we obtain an \u03a9(\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>\u03f5<\/jats:sup>\n            ) hardness bound for the undirected subset\n            <jats:italic>k<\/jats:italic>\n            -connectivity problem. Additionally, we give a result on the integrality ratio of the natural linear programming relaxation of the directed rooted\n            <jats:italic>k<\/jats:italic>\n            -connectivity problem.\n          <\/jats:p>","DOI":"10.1145\/2650183","type":"journal-article","created":{"date-parts":[[2014,10,31]],"date-time":"2014-10-31T19:28:54Z","timestamp":1414783734000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Approximating Rooted Steiner Networks"],"prefix":"10.1145","volume":"11","author":[{"given":"Joseph","family":"Cheriyan","sequence":"first","affiliation":[{"name":"University of Waterloo, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bundit","family":"Laekhanukit","sequence":"additional","affiliation":[{"name":"McGill University, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guyslain","family":"Naves","sequence":"additional","affiliation":[{"name":"McGill University, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adrian","family":"Vetta","sequence":"additional","affiliation":[{"name":"McGill University, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,10,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"e_1_2_1_3_1","unstructured":"P. Berman M. Karpinski and A. Scott. 2003. Approximation hardness of short symmetric instances of MAX-3SAT. Electronic Colloquium on Computational Complexity TR03--049.  P. Berman M. Karpinski and A. Scott. 2003. Approximation hardness of short symmetric instances of MAX-3SAT. Electronic Colloquium on Computational Complexity TR03--049."},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"J. Cheriyan B. Laekhanukit G. Naves and A. Vetta. 2012. Approximating rooted Steiner networks. In SODA. 1499--1511.   J. Cheriyan B. Laekhanukit G. Naves and A. Vetta. 2012. Approximating rooted Steiner networks. In SODA. 1499--1511.","DOI":"10.1137\/1.9781611973099.119"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.63"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1747597.1748059"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374403"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1042"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301447"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010302"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704441241"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-1324-4"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780628"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930170004"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702416736"},{"key":"e_1_2_1_17_1","unstructured":"B. Laekhanukit. 2011. An improved approximation algorithm for the minimum-cost subset k-connected subgraph problem. CoRR abs\/1104.3923.  B. Laekhanukit. 2011. An improved approximation algorithm for the minimum-cost subset k-connected subgraph problem. CoRR abs\/1104.3923."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.01.036"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2009.07.011"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2390176.2390177"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795280895"},{"key":"e_1_2_1_22_1","volume-title":"Approximation Algorithms","author":"Vazirani V.","unstructured":"V. Vazirani . Approximation Algorithms . Springer , Berlin . V. Vazirani. Approximation Algorithms. Springer, Berlin."},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"D. Williamson and D. Shmoys. 2010. The Design of Approximation Algorithms. Cambridge University Press.   D. Williamson and D. Shmoys. 2010. The Design of Approximation Algorithms. Cambridge University Press.","DOI":"10.1017\/CBO9780511921735"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2650183","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2650183","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:11:54Z","timestamp":1750227114000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2650183"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10,30]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,11,17]]}},"alternative-id":["10.1145\/2650183"],"URL":"https:\/\/doi.org\/10.1145\/2650183","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,10,30]]},"assertion":[{"value":"2012-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-10-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}