{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:05:48Z","timestamp":1750694748103,"version":"3.37.3"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2019,4,25]],"date-time":"2019-04-25T00:00:00Z","timestamp":1556150400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,4,25]],"date-time":"2019-04-25T00:00:00Z","timestamp":1556150400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"crossref","award":["RGPIN-2014-04351"],"award-info":[{"award-number":["RGPIN-2014-04351"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2020,7]]},"DOI":"10.1007\/s10107-019-01394-z","type":"journal-article","created":{"date-parts":[[2019,4,25]],"date-time":"2019-04-25T06:05:32Z","timestamp":1556172332000},"page":"315-354","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["The matching augmentation problem: a $$\\frac{7}{4}$$-approximation algorithm"],"prefix":"10.1007","volume":"182","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0316-7650","authenticated-orcid":false,"given":"J.","family":"Cheriyan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J.","family":"Dippel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"F.","family":"Grandoni","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A.","family":"Khan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"V. V.","family":"Narayan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,4,25]]},"reference":[{"key":"1394_CR1","first-page":"2384","volume-title":"Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017","author":"D Adjiashvili","year":"2017","unstructured":"Adjiashvili, D.: Beating approximation factor two for weighted tree augmentation with bounded costs. In: Klein, P.N. (ed.) Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, pp. 2384\u20132399. SIAM, Philadelphia (2017)"},{"key":"1394_CR2","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14279-6","volume-title":"Graph Theory","author":"R Diestel","year":"2010","unstructured":"Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173, 4th edn. Springer, Heidelberg (2010)","edition":"4"},{"issue":"2","key":"1394_CR3","doi-asserted-by":"publisher","first-page":"21","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 (2009)","journal-title":"ACM Trans. Algorithms"},{"key":"1394_CR4","volume-title":"Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018","author":"S Fiorini","year":"2018","unstructured":"Fiorini, S., Gro\u00df, M., K\u00f6nemann, J., Sanit\u00e0, L.: Approximating weighted tree augmentation via Chv\u00e1tal\u2013Gomory cuts. In: Czumaj, A. (ed.) Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018. SIAM, Philadelphia (2018)"},{"issue":"2","key":"1394_CR5","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":"1394_CR6","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(82)90059-7","volume":"19","author":"GN Frederickson","year":"1982","unstructured":"Frederickson, G.N., J\u00e1J\u00e1, J.: On the relationship between the biconnectivity augmentation and traveling salesman problems. Theor. Comput. Sci. 19, 189\u2013201 (1982)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"1394_CR7","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1002\/net.20289","volume":"53","author":"HN Gabow","year":"2009","unstructured":"Gabow, H.N., Goemans, M.X., Tardos, \u00c9., Williamson, D.P.: Approximating the smallest $$k$$-edge connected spanning subgraph by LP-rounding. Networks 53(4), 345\u2013357 (2009)","journal-title":"Networks"},{"issue":"2","key":"1394_CR8","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1137\/S0097539793242618","volume":"24","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: A general approximation technique for constrained forest problems. SIAM J. Comput. 24(2), 296\u2013317 (1995)","journal-title":"SIAM J. Comput."},{"key":"1394_CR9","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"},{"issue":"1","key":"1394_CR10","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)","journal-title":"Combinatorica"},{"issue":"8","key":"1394_CR11","doi-asserted-by":"publisher","first-page":"1665","DOI":"10.1016\/j.jcss.2015.06.003","volume":"81","author":"M Karpinski","year":"2015","unstructured":"Karpinski, M., Lampis, M., Schmied, R.: New inapproximability bounds for TSP. J. Comput. Syst. Sci. 81(8), 1665\u20131677 (2015)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"1394_CR12","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)","journal-title":"ACM Trans. Algorithms"},{"key":"1394_CR13","series-title":"Cambridge Texts in Applied Mathematics (No. 46)","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511977152","volume-title":"Iterative Methods in Combinatorial Optimization","author":"LC Lau","year":"2011","unstructured":"Lau, L.C., Ravi, R., Singh, M.: Iterative Methods in Combinatorial Optimization. Cambridge Texts in Applied Mathematics (No. 46). Cambridge University Press, Cambridge (2011)"},{"key":"1394_CR14","volume-title":"Matching Theory, volume 367 of AMS\/Chelsea Publishing","author":"L Lov\u00e0sz","year":"2009","unstructured":"Lov\u00e0sz, L., Plummer, M.D.: Matching Theory, volume 367 of AMS\/Chelsea Publishing. American Mathematical Society, Providence (2009)"},{"key":"1394_CR15","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. Discrete Appl. Math. 126, 83\u2013113 (2003)","journal-title":"Discrete Appl. Math."},{"key":"1394_CR16","series-title":"Algorithms and Combinatorics","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics, vol. 24. Springer, Berlin (2003)"},{"issue":"5","key":"1394_CR17","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1007\/s00493-014-2960-3","volume":"34","author":"A Seb\u00f6","year":"2014","unstructured":"Seb\u00f6, 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)","journal-title":"Combinatorica"},{"key":"1394_CR18","first-page":"262","volume-title":"Approximation Algorithms for Combinatorial Optimization, Third International Workshop, APPROX 2000, Proceedings, LNCS 1913","author":"S Vempala","year":"2000","unstructured":"Vempala, S., Vetta, A.: Factor 4\/3 approximations for minimum 2-connected subgraphs. In: Jansen, K., Khuller, S. (eds.) Approximation Algorithms for Combinatorial Optimization, Third International Workshop, APPROX 2000, Proceedings, LNCS 1913, pp. 262\u2013273. Springer, Berlin (2000)"},{"key":"1394_CR19","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1090\/S0002-9947-1932-1501641-2","volume":"34","author":"H Whitney","year":"1932","unstructured":"Whitney, H.: Non-separable and planar graphs. Trans. Am. Math. Soc. 34, 339\u2013362 (1932)","journal-title":"Trans. Am. Math. Soc."},{"key":"1394_CR20","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511921735","volume-title":"The Design of Approximation Algorithms","author":"DP Williamson","year":"2011","unstructured":"Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms. Cambridge University Press, Cambridge (2011)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-019-01394-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-019-01394-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-019-01394-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,23]],"date-time":"2020-06-23T15:14:52Z","timestamp":1592925292000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-019-01394-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,25]]},"references-count":20,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2020,7]]}},"alternative-id":["1394"],"URL":"https:\/\/doi.org\/10.1007\/s10107-019-01394-z","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2019,4,25]]},"assertion":[{"value":"28 December 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 April 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 April 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}