2026-07-23T17:27:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15471 2024-03-06T10:55:22Z ddc:004 open_access

An Improved Approximation Algorithm for the Matching Augmentation Problem Cheriyan, Joseph Cummings, Robert Dippel, Jack Zhu, Jasper 2-Edge connected graph 2-edge covers approximation algorithms connectivity augmentation forest augmentation problem matching augmentation problem network design We present a 5/3-approximation algorithm for the matching augmentation problem (MAP): given a multi-graph with edges of cost either zero or one such that the edges of cost zero form a matching, find a 2-edge connected spanning subgraph (2-ECSS) of minimum cost. A 7/4-approximation algorithm for the same problem was presented recently, see Cheriyan, et al., "The matching augmentation problem: a 7/4-approximation algorithm," Math. Program., 182(1):315-354, 2020. Our improvement is based on new algorithmic techniques, and some of these may lead to advances on related problems. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Joseph Cheriyan and Robert Cummings and Jack Dippel and Jasper Zhu 2021 Is Part Of LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2021.38 urn:nbn:de:0030-drops-154714 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.38 eng https://creativecommons.org/licenses/by/4.0/legalcode