An Improved Approximation Algorithm for the Matching Augmentation Problem

J. Cheriyan, R. Cummings, J. Dippel +1

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