{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,23]],"date-time":"2026-07-23T23:51:04Z","timestamp":1784850664028,"version":"3.55.0"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2021,5,20]],"date-time":"2021-05-20T00:00:00Z","timestamp":1621468800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,5,20]],"date-time":"2021-05-20T00:00:00Z","timestamp":1621468800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"name":"DFG","award":["RTG 1855"],"award-info":[{"award-number":["RTG 1855"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2022,3]]},"DOI":"10.1007\/s10107-021-01664-9","type":"journal-article","created":{"date-parts":[[2021,5,20]],"date-time":"2021-05-20T14:02:47Z","timestamp":1621519367000},"page":"409-441","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Flexible Graph Connectivity"],"prefix":"10.1007","volume":"192","author":[{"given":"David","family":"Adjiashvili","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Felix","family":"Hommelsheim","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Moritz","family":"M\u00fchlenthaler","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,5,20]]},"reference":[{"issue":"2","key":"1664_CR1","first-page":"19","volume":"15","author":"D Adjiashvili","year":"2018","unstructured":"Adjiashvili, D.: Beating approximation factor two for weighted tree augmentation with bounded costs. ACM Trans. Algorithms (TALG) 15(2), 19 (2018)","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"1664_CR2","doi-asserted-by":"crossref","unstructured":"Adjiashvili, D., Bosio, S., Weismantel, R., Zenklusen, R.: Time-expanded packings. In: International Colloquium on Automata. Languages, and Programming, pp. 64\u201376. Springer, Berlin (2014)","DOI":"10.1007\/978-3-662-43948-7_6"},{"key":"1664_CR3","doi-asserted-by":"crossref","unstructured":"Adjiashvili, D., Hommelsheim, F., M\u00fchlenthaler, M.: Flexible graph connectivity. arXiv:1910.13297 (2019)","DOI":"10.1007\/978-3-030-45771-6_2"},{"key":"1664_CR4","doi-asserted-by":"crossref","unstructured":"Adjiashvili, D., Hommelsheim, F., M\u00fchlenthaler, M.: Flexible graph connectivity. In International Conference on Integer Programming and Combinatorial Optimization, pp. 13\u201326 (2020)","DOI":"10.1007\/978-3-030-45771-6_2"},{"issue":"1\u20132","key":"1664_CR5","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1007\/s10107-014-0760-6","volume":"149","author":"D Adjiashvili","year":"2015","unstructured":"Adjiashvili, D., Stiller, S., Zenklusen, R.: Bulk-robust combinatorial optimization. Math. Program. 149(1\u20132), 361\u2013390 (2015). https:\/\/doi.org\/10.1007\/s10107-014-0760-6","journal-title":"Math. Program."},{"issue":"2","key":"1664_CR6","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1007\/s00453-013-9862-4","volume":"72","author":"D Chakrabarty","year":"2015","unstructured":"Chakrabarty, D., Chekuri, C., Khanna, S., Korula, N.: Approximability of capacitated network design. Algorithmica 72(2), 493\u2013514 (2015)","journal-title":"Algorithmica"},{"key":"1664_CR7","doi-asserted-by":"crossref","unstructured":"Chakrabarty, D., Krishnaswamy, R., Li, S., Narayanan, S.: Capacitated network design on undirected graphs. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pp. 71\u201380. Springer, Berlin (2013)","DOI":"10.1007\/978-3-642-40328-6_6"},{"key":"1664_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-019-01394-z","author":"J Cheriyan","year":"2019","unstructured":"Cheriyan, J., Dippel, J., Grandoni, F., Khan, A., Narayan, V.: The matching augmentation problem: a $$\\frac{7}{4}$$-approximation algorithm. Math. Program. (2019). https:\/\/doi.org\/10.1007\/s10107-019-01394-z","journal-title":"Math. Program."},{"issue":"2","key":"1664_CR9","doi-asserted-by":"publisher","first-page":"528","DOI":"10.1137\/S009753979833920X","volume":"30","author":"J Cheriyan","year":"2000","unstructured":"Cheriyan, J., Thurimella, R.: Approximating minimum-size k-connected spanning subgraphs via matching. SIAM J. Comput. 30(2), 528\u2013560 (2000)","journal-title":"SIAM J. Comput."},{"key":"1664_CR10","doi-asserted-by":"crossref","unstructured":"Fiorini, S., Gro\u00df, M., K\u00f6nemann, J., Sanit\u00e0, L.: Approximating weighted tree augmentation via Chv\u00e1tal\u2013Gomory cuts. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201918, pp. 817\u2013831 (2018)","DOI":"10.1137\/1.9781611975031.53"},{"issue":"2","key":"1664_CR11","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). https:\/\/doi.org\/10.1137\/0210019","journal-title":"SIAM J. Comput."},{"issue":"1","key":"1664_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0895480102414910","volume":"19","author":"HN Gabow","year":"2005","unstructured":"Gabow, H.N.: An improved analysis for approximating the smallest k-edge connected spanning subgraph of a multigraph. SIAM J. Discrete Math. 19(1), 1\u201318 (2005)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"1664_CR13","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1137\/080732572","volume":"41","author":"HN Gabow","year":"2012","unstructured":"Gabow, H.N., Gallagher, S.R.: Iterated rounding algorithms for the smallest $$k$$-edge connected spanning subgraph. SIAM J. Comput. 41(1), 61\u2013103 (2012)","journal-title":"SIAM J. Comput."},{"key":"1664_CR14","unstructured":"Goemans, M.X., Goldberg, A.V., Plotkin, S.A., Shmoys, D.B., Tardos, \u00c9., Williamson, D.P.: Improved approximation algorithms for network design problems. In: Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 223\u2013232 (1994)"},{"key":"1664_CR15","doi-asserted-by":"publisher","unstructured":"Grandoni, F., Kalaitzis, C., Zenklusen, R.: Improved approximation for tree augmentation: saving by rewiring. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, New York, NY, USA, pp. 632\u2013645. ACM (2018). https:\/\/doi.org\/10.1145\/3188745.3188898","DOI":"10.1145\/3188745.3188898"},{"issue":"1","key":"1664_CR16","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(1), 39\u201360 (2001). https:\/\/doi.org\/10.1007\/s004930170004","journal-title":"Combinatorica"},{"issue":"6","key":"1664_CR17","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1145\/950620.950621","volume":"50","author":"K Jain","year":"2003","unstructured":"Jain, K., Mahdian, M., Markakis, E., Saberi, A., Vazirani, V.V.: Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. J. ACM 50(6), 795\u2013824 (2003). https:\/\/doi.org\/10.1145\/950620.950621","journal-title":"J. ACM"},{"issue":"2","key":"1664_CR18","doi-asserted-by":"publisher","first-page":"23","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 (2016). https:\/\/doi.org\/10.1145\/2786981","journal-title":"ACM Trans. Algorithms"},{"key":"1664_CR19","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. Discrete Appl. Math. 239, 94\u2013105 (2018). https:\/\/doi.org\/10.1016\/j.dam.2017.12.033","journal-title":"Discrete Appl. Math."},{"key":"1664_CR20","unstructured":"Nutov, Z.: On the tree augmentation problem. In: 25th Annual European Symposium on Algorithms (ESA 2017), vol.\u00a087, p.\u00a061 (2017)"},{"issue":"5","key":"1664_CR21","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1007\/s00493-014-2960-3","volume":"34","author":"A Seb\u0151","year":"2014","unstructured":"Seb\u0151, A., Vygen, J.: Shorter tours by nicer ears: 7\/5-approximation for the graph-tsp, 3\/2 for the path version, and 4\/3 for two-edge-connected subgraphs. Combinatorica 34(5), 597\u2013629 (2014). https:\/\/doi.org\/10.1007\/s00493-014-2960-3","journal-title":"Combinatorica"},{"key":"1664_CR22","unstructured":"The Optimization Firm. baron (2019). https:\/\/minlp.com\/baron"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01664-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-021-01664-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01664-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,9]],"date-time":"2022-03-09T17:18:28Z","timestamp":1646846308000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-021-01664-9"}},"subtitle":["Approximating network design problems between 1- and 2-connectivity"],"short-title":[],"issued":{"date-parts":[[2021,5,20]]},"references-count":22,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["1664"],"URL":"https:\/\/doi.org\/10.1007\/s10107-021-01664-9","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,5,20]]},"assertion":[{"value":"22 June 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 April 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 May 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}