An Improved Approximation Algorithm for the Matching Augmentation Problem
Joseph Cheriyan, R. Cummings, Jack Dippel, Jiashuang Zhu · SIAM Journal on Discrete Mathematics · 2023
Abstract. We present a [Formula: see text]-approximation algorithm for the matching augmentation problem (MAP): given a multigraph 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 [Formula: see text]-approximation algorithm for the same problem was presented recently; see Cheriyan et al. [ Math. Program., 182 (2020), pp. 315–354]. Our improvement is based on new algorithmic techniques, and some of these may lead to advances on related problems.