AN IMPROVED APPROXIMATION ALGORITHM FOR THE MATCHING AUGMENTATION PROBLEM.

We present a 5/3-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 7/4-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. [ABSTRACT FROM AUTHOR]