{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:58Z","timestamp":1740109318043,"version":"3.37.3"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2023,9,26]],"date-time":"2023-09-26T00:00:00Z","timestamp":1695686400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,9,26]],"date-time":"2023-09-26T00:00:00Z","timestamp":1695686400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","award":["200021_184622"],"award-info":[{"award-number":["200021_184622"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100019180","name":"HORIZON EUROPE European Research Council","doi-asserted-by":"publisher","award":["817750"],"award-info":[{"award-number":["817750"]}],"id":[{"id":"10.13039\/100019180","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2024,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The Connectivity Augmentation Problem (CAP) together with a well-known special case thereof known as the Tree Augmentation Problem (TAP) are among the most basic Network Design problems. There has been a surge of interest recently to find approximation algorithms with guarantees below 2 for both TAP and CAP, culminating in the currently best approximation factor for both problems of 1.393 through quite sophisticated techniques. We present a new and arguably simple matching-based method for the well-known special case of leaf-to-leaf instances. Combining our work with prior techniques, we readily obtain a <jats:inline-formula><jats:alternatives><jats:tex-math>$$(4\/3+\\varepsilon )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mn>4<\/mml:mn>\n                    <mml:mo>\/<\/mml:mo>\n                    <mml:mn>3<\/mml:mn>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mi>\u03b5<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-approximation for Leaf-to-Leaf CAP by returning the better of our solution and one of an existing method. Prior to our work, a <jats:inline-formula><jats:alternatives><jats:tex-math>$$4\/3$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>4<\/mml:mn>\n                    <mml:mo>\/<\/mml:mo>\n                    <mml:mn>3<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-guarantee was only known for Leaf-to-Leaf TAP instances on trees of height 2. Moreover, when combining our technique with a recently introduced stack analysis approach, which is part of the above-mentioned 1.393-approximation, we can further improve the approximation factor to 1.29, obtaining for the first time a factor below <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\frac{4}{3}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mfrac>\n                    <mml:mn>4<\/mml:mn>\n                    <mml:mn>3<\/mml:mn>\n                  <\/mml:mfrac>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for a nontrivial class of TAP\/CAP instances.\n<\/jats:p>","DOI":"10.1007\/s10107-023-02018-3","type":"journal-article","created":{"date-parts":[[2023,9,26]],"date-time":"2023-09-26T14:02:06Z","timestamp":1695736926000},"page":"515-549","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Better-than-$$\\frac{4}{3}$$-approximations for leaf-to-leaf tree and connectivity augmentation"],"prefix":"10.1007","volume":"207","author":[{"given":"Federica","family":"Cecchetto","sequence":"first","affiliation":[]},{"given":"Vera","family":"Traub","sequence":"additional","affiliation":[]},{"given":"Rico","family":"Zenklusen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,9,26]]},"reference":[{"issue":"2","key":"2018_CR1","first-page":"19:1","volume":"15","author":"D Adjiashvili","year":"2018","unstructured":"Adjiashvili, D.: Beating approximation factor two for weighted tree augmentation with bounded costs. ACM Trans. Algorithms 15(2), 19:1-19:26 (2018)","journal-title":"ACM Trans. Algorithms"},{"key":"2018_CR2","doi-asserted-by":"crossref","unstructured":"Basavaraju, M., Fomin, F.V., Golovach, P., Misra, P., Ramanujan, M.S., Saurabh, S.: Parameterized algorithms to preserve connectivity. In: Proceedings of 41st International Colloquium on Automata, Languages, and Programming (ICALP), pp. 800\u2013811 (2014)","DOI":"10.1007\/978-3-662-43948-7_66"},{"key":"2018_CR3","doi-asserted-by":"crossref","unstructured":"Cecchetto, F., Traub, V., Zenklusen, R.: Bridging the gap between tree and connectivity augmentation: Unified and stronger approaches. https:\/\/arxiv.org\/abs\/2012.00086v3 (2020). A short version appeared in the proceedings of STOC 2021","DOI":"10.1145\/3406325.3451086"},{"issue":"2","key":"2018_CR4","doi-asserted-by":"publisher","first-page":"608","DOI":"10.1007\/s00453-017-0275-7","volume":"80","author":"J Cheriyan","year":"2018","unstructured":"Cheriyan, J., Gao, Z.: Approximating (unweighted) tree augmentation via lift-and-project, part II. Algorithmica 80(2), 608\u2013651 (2018). https:\/\/doi.org\/10.1007\/s00453-017-0275-7","journal-title":"Algorithmica"},{"issue":"2","key":"2018_CR5","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1007\/s00453-016-0270-4","volume":"80","author":"J Cheriyan","year":"2018","unstructured":"Cheriyan, J., Gao, Z.: Approximating (unweighted) tree augmentation via lift-and-project, part I: stemless TAP. Algorithmica 80(2), 530\u2013559 (2018)","journal-title":"Algorithmica"},{"key":"2018_CR6","doi-asserted-by":"crossref","unstructured":"Cheriyan, J., Jord\u00e1n, T., Ravi, R.: On 2-coverings and 2-packings of laminar families. In: Proceedings of 7th Annual European Symposium on Algorithms (ESA), pp. 510\u2013520 (1999)","DOI":"10.1007\/3-540-48481-7_44"},{"issue":"4","key":"2018_CR7","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1016\/j.orl.2008.01.009","volume":"36","author":"J Cheriyan","year":"2008","unstructured":"Cheriyan, J., Karloff, H., Khandekar, R., K\u00f6nemann, J.: On the integrality ratio for tree augmentation. Oper. Res. Lett. 36(4), 399\u2013401 (2008)","journal-title":"Oper. Res. Lett."},{"key":"2018_CR8","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/j.tcs.2013.04.004","volume":"489","author":"N Cohen","year":"2013","unstructured":"Cohen, N., Nutov, Z.: A $$(1+ \\ln 2)$$-approximation algorithm for minimum-cost $$2$$-edge-connectivity augmentation of trees with constant radius. Theor. Comput. Sci. 489, 67\u201374 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"2018_CR9","unstructured":"Dinitz, E.A., Karzanov, A.V., Lomonosov, M.V.: On the structure of the system of minimum edge cuts of a graph. Studies in Discrete Optimization, pp. 290\u2013306 (1976)"},{"issue":"2","key":"2018_CR10","doi-asserted-by":"publisher","first-page":"21:1","DOI":"10.1145\/1497290.1497297","volume":"5","author":"G Even","year":"2009","unstructured":"Even, G., Feldman, J., Kortsarz, G., Nutov, Z.: A $$1.8$$ approximation algorithm for augmenting edge-connectivity of a graph from $$1$$ to $$2$$. ACM Trans. Algorithms 5(2), 21:1-21:17 (2009)","journal-title":"ACM Trans. Algorithms"},{"key":"2018_CR11","doi-asserted-by":"crossref","unstructured":"Fiorini, S., Gro\u00df, M., K\u00f6nemann, J., Sanit\u00e0, L.: Approximating weighted tree augmentation via Chv\u00e1tal-Gomory Cuts. In: Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 817\u2013831 (2018)","DOI":"10.1137\/1.9781611975031.53"},{"issue":"6","key":"2018_CR12","doi-asserted-by":"publisher","first-page":"1242","DOI":"10.1016\/j.dam.2008.03.040","volume":"157","author":"A Frank","year":"2009","unstructured":"Frank, A.: Rooted k-connections in digraphs. Discret. Appl. Math. 157(6), 1242\u20131254 (2009). https:\/\/doi.org\/10.1016\/j.dam.2008.03.040","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"2018_CR13","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1137\/0210019","volume":"10","author":"GN Frederickson","year":"1981","unstructured":"Frederickson, G.N., J\u00e1J\u00e1, J.: Approximation algorithms for several graph augmentation problems. SIAM J. Comput. 10(2), 270\u2013283 (1981)","journal-title":"SIAM J. Comput."},{"key":"2018_CR14","unstructured":"Garg, M., Grandoni, F., Jabal\u00a0Ameli, A.: Improved approximation for two-edge-connectivity (2022). arxiv:2209.10265v2"},{"key":"2018_CR15","unstructured":"Goemans, M.X., Goldberg, A.V., Plotkin, S., Shmoys, D.B., Tardos, E., Williamson, D.P.: Improved approximation algorithms for network design problems. In: Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 223\u2013232 (1994)"},{"key":"2018_CR16","doi-asserted-by":"crossref","unstructured":"Grandoni, F., Kalaitzis, C., Zenklusen, R.: Improved approximation for tree augmentation: saving by rewiring. In: Proceedings of 50th ACM Symposium on Theory of Computing (STOC), pp. 632\u2013645 (2018)","DOI":"10.1145\/3188745.3188898"},{"key":"2018_CR17","doi-asserted-by":"crossref","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics, vol.\u00a02, 2nd corrected edn. Springer (1993)","DOI":"10.1007\/978-3-642-78240-4"},{"key":"2018_CR18","unstructured":"Iglesias, J., Ravi, R.: Coloring down: $$3\/2$$-approximation for special cases of the weighted tree augmentation problem. arxiv:1707.05240 (2018)"},{"key":"2018_CR19","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/s004930170004","volume":"21","author":"K Jain","year":"2001","unstructured":"Jain, K.: A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica 21, 39\u201360 (2001)","journal-title":"Combinatorica"},{"issue":"2","key":"2018_CR20","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1006\/jagm.1993.1010","volume":"14","author":"S Khuller","year":"1993","unstructured":"Khuller, S., Thurimella, R.: Approximation algorithms for graph augmentation. J. Algorithms 14(2), 214\u2013225 (1993)","journal-title":"J. Algorithms"},{"issue":"3","key":"2018_CR21","doi-asserted-by":"publisher","first-page":"704","DOI":"10.1137\/S0097539702416736","volume":"33","author":"G Kortsarz","year":"2004","unstructured":"Kortsarz, G., Krauthgamer, R., Lee, J.R.: Hardness of approximation for vertex-connectivity network design problems. SIAM J. Comput. 33(3), 704\u2013720 (2004)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"2018_CR22","doi-asserted-by":"publisher","first-page":"23:1","DOI":"10.1145\/2786981","volume":"12","author":"G Kortsarz","year":"2016","unstructured":"Kortsarz, G., Nutov, Z.: A simplified $$1.5$$-approximation algorithm for augmenting edge-connectivity of a graph from $$1$$ to $$2$$. ACM Trans. Algorithms 12(2), 23:1-23:20 (2016)","journal-title":"ACM Trans. Algorithms"},{"key":"2018_CR23","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1016\/j.dam.2017.12.033","volume":"239","author":"G Kortsarz","year":"2018","unstructured":"Kortsarz, G., Nutov, Z.: LP-relaxations for tree augmentation. Discret. Appl. Math. 239, 94\u2013105 (2018)","journal-title":"Discret. Appl. Math."},{"key":"2018_CR24","doi-asserted-by":"publisher","first-page":"1424","DOI":"10.1016\/j.dam.2010.04.002","volume":"158","author":"Y Maduel","year":"2010","unstructured":"Maduel, Y., Nutov, Z.: Covering a laminar family by leaf to leaf links. Discret. Appl. Math. 158, 1424\u20131432 (2010)","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"2018_CR25","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/S0166-218X(02)00218-4","volume":"126","author":"H Nagamochi","year":"2003","unstructured":"Nagamochi, H.: An approximation for finding a smallest $$2$$-edge-connected subgraph containing a specified spanning tree. Discret. Appl. Math. 126(1), 83\u2013113 (2003)","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"2018_CR26","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1007\/s00453-020-00765-9","volume":"83","author":"Z Nutov","year":"2020","unstructured":"Nutov, Z.: On the tree augmentation problem. Algorithmica 83(2), 553\u2013575 (2020). https:\/\/doi.org\/10.1007\/s00453-020-00765-9","journal-title":"Algorithmica"},{"key":"2018_CR27","doi-asserted-by":"crossref","unstructured":"Nutov, Z.: Approximation algorithms for connectivity augmentation problems. In: Proceedings of the 16th International Computer Science Symposium in Russia (CSR), pp. 321\u2013338 (2021)","DOI":"10.1007\/978-3-030-79416-3_19"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-02018-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-023-02018-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-02018-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,7]],"date-time":"2024-08-07T15:05:49Z","timestamp":1723043149000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-023-02018-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,26]]},"references-count":27,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2024,9]]}},"alternative-id":["2018"],"URL":"https:\/\/doi.org\/10.1007\/s10107-023-02018-3","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2023,9,26]]},"assertion":[{"value":"4 May 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 August 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 September 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}