The Matching Augmentation Problem: A $\frac{7}{4}$-Approximation Algorithm

Joe Cheriyan, Jack Dippel, Fabrizio Grandoni +2

We present a $\frac{7}{4}$ 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 ze…