{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T11:56:46Z","timestamp":1781092606544,"version":"3.54.1"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2011,3,1]],"date-time":"2011-03-01T00:00:00Z","timestamp":1298937600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001742","name":"United States-Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2002276"],"award-info":[{"award-number":["2002276"]}],"id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0728782CNS-0721899CCF-0448095CCF-0729022"],"award-info":[{"award-number":["CCF-0728782CNS-0721899CCF-0448095CCF-0729022"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["CCF-0728782CNS-0721899CCF-0448095CCF-0729022"],"award-info":[{"award-number":["CCF-0728782CNS-0721899CCF-0448095CCF-0729022"]}],"id":[{"id":"10.13039\/100000144","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":[[2011,3]]},"abstract":"<jats:p>\n            In the\n            <jats:italic>generalized connectivity<\/jats:italic>\n            problem, we are given an edge-weighted graph\n            <jats:italic>G<\/jats:italic>\n            = (\n            <jats:italic>V<\/jats:italic>\n            ,\n            <jats:italic>E<\/jats:italic>\n            ) and a collection\n            <jats:italic>D<\/jats:italic>\n            = {(\n            <jats:italic>S<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            ,\n            <jats:italic>T<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            ), \u2026, (\n            <jats:italic>S<\/jats:italic>\n            <jats:sub>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sub>\n            ,\n            <jats:italic>T<\/jats:italic>\n            <jats:sub>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sub>\n            )} of distinct\n            <jats:italic>demands<\/jats:italic>\n            each demand (\n            <jats:italic>S<\/jats:italic>\n            <jats:sub>\n              <jats:italic>i<\/jats:italic>\n            <\/jats:sub>\n            ,\n            <jats:italic>T<\/jats:italic>\n            <jats:sub>\n              <jats:italic>i<\/jats:italic>\n            <\/jats:sub>\n            ) is a pair of disjoint vertex subsets. We say that a subgraph\n            <jats:italic>F<\/jats:italic>\n            of\n            <jats:italic>G<\/jats:italic>\n            <jats:italic>connects<\/jats:italic>\n            a demand (\n            <jats:italic>S<\/jats:italic>\n            <jats:sub>\n              <jats:italic>i<\/jats:italic>\n            <\/jats:sub>\n            ,\n            <jats:italic>T<\/jats:italic>\n            <jats:sub>\n              <jats:italic>i<\/jats:italic>\n            <\/jats:sub>\n            ) when it contains a path with one endpoint in\n            <jats:italic>S<\/jats:italic>\n            <jats:sub>\n              <jats:italic>i<\/jats:italic>\n            <\/jats:sub>\n            and the other in\n            <jats:italic>T<\/jats:italic>\n            <jats:sub>\n              <jats:italic>i<\/jats:italic>\n            <\/jats:sub>\n            . The goal is to identify a minimum weight subgraph that connects all demands in\n            <jats:italic>D<\/jats:italic>\n            . Alon et al. (SODA '04) introduced this problem to study online network formation settings and showed that it captures some well-studied problems such as Steiner forest, facility location with nonmetric costs, tree multicast, and group Steiner tree. Obtaining a nontrivial approximation ratio for generalized connectivity was left as an open problem. We describe the first poly-logarithmic approximation algorithm for generalized connectivity that has a performance guarantee of\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>k<\/jats:italic>\n            ). Here,\n            <jats:italic>n<\/jats:italic>\n            is the number of vertices in\n            <jats:italic>G<\/jats:italic>\n            and\n            <jats:italic>k<\/jats:italic>\n            is the number of demands. We also prove that the cut-covering relaxation of this problem has an\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:sup>3<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>k<\/jats:italic>\n            ) integrality gap.\n          <\/jats:p>\n          <jats:p>\n            Building upon the results for generalized connectivity, we obtain improved approximation algorithms for two problems that contain generalized connectivity as a special case. For the\n            <jats:italic>directed Steiner network<\/jats:italic>\n            problem, we obtain an\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>1\/2 + \u03f5<\/jats:sup>\n            ) approximation which improves on the currently best performance guarantee of\n            <jats:italic>\u00d5<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>2\/3<\/jats:sup>\n            ) due to Charikar et al. (SODA '98). For the\n            <jats:italic>set connector<\/jats:italic>\n            problem, recently introduced by Fukunaga and Nagamochi (IPCO '07), we present a poly-logarithmic approximation; this result improves on the previously known ratio which can be \u03a9(\n            <jats:italic>n<\/jats:italic>\n            ) in the worst case.\n          <\/jats:p>","DOI":"10.1145\/1921659.1921664","type":"journal-article","created":{"date-parts":[[2011,3,29]],"date-time":"2011-03-29T12:01:30Z","timestamp":1301400090000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":34,"title":["Set connectivity problems in undirected graphs and the directed steiner network problem"],"prefix":"10.1145","volume":"7","author":[{"given":"Chandra","family":"Chekuri","sequence":"first","affiliation":[{"name":"University of Illinois, Urbana, IL"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Guy","family":"Even","sequence":"additional","affiliation":[{"name":"Tel-Aviv University, Tel-Aviv, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anupam","family":"Gupta","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Danny","family":"Segev","sequence":"additional","affiliation":[{"name":"University of Haifa, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2011,3,31]]},"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":"publisher","DOI":"10.1145\/1198513.1198522"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/874062.875536"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276725"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1042"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.15"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms. 1265--1274","author":"Chekuri C.","unstructured":"Chekuri , C. , Hajiaghayi , M. T. , Kortsarz , G. , and Salavatipour , M. R . 2007. Approximation algorithms for node-weighted buy-at-bulk network design . In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms. 1265--1274 . Chekuri, C., Hajiaghayi, M. T., Kortsarz, G., and Salavatipour, M. R. 2007. Approximation algorithms for node-weighted buy-at-bulk network design. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms. 1265--1274."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301447"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.011"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72792-7_36"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1096"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793242618"},{"key":"e_1_2_1_13_1","unstructured":"Goemans M. X. and Williamson D. P. 1996. The primal-dual method for approximation algorithms and its application to network design problems. In Approximation Algorithms for NP-Hard Problems D. S. Hochbaum Ed. PWS Publishing Company.   Goemans M. X. and Williamson D. P. 1996. The primal-dual method for approximation algorithms and its application to network design problems. In Approximation Algorithms for NP-Hard Problems D. S. Hochbaum Ed. PWS Publishing Company."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11830924_16"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704445718"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780628"},{"key":"e_1_2_1_17_1","volume-title":"1996. Approximation Algorithms for NP-Hard Problems","author":"Hochbaum D. S.","unstructured":"Hochbaum , D. S. , Ed. 1996. Approximation Algorithms for NP-Hard Problems . PWS Publishing Company . Hochbaum, D. S., Ed. 1996. Approximation Algorithms for NP-Hard Problems. PWS Publishing Company."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80044-9"},{"key":"e_1_2_1_19_1","volume-title":"Approximation Algorithms","author":"Vazirani V. V.","unstructured":"Vazirani , V. V. 2001. Approximation Algorithms . Springer . Vazirani, V. V. 2001. Approximation Algorithms. Springer."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523690"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms. 59--63","author":"Zosin L.","unstructured":"Zosin , L. and Khuller , S . 2002. On directed Steiner trees . In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms. 59--63 . Zosin, L. and Khuller, S. 2002. On directed Steiner trees. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms. 59--63."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1921659.1921664","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1921659.1921664","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:26:08Z","timestamp":1750278368000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1921659.1921664"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,3]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,3]]}},"alternative-id":["10.1145\/1921659.1921664"],"URL":"https:\/\/doi.org\/10.1145\/1921659.1921664","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,3]]},"assertion":[{"value":"2008-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-03-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}