An Improved Approximation Algorithm for the Matching Augmentation Problem

07/22/2020
by   J. Cheriyan, et al.
0

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; arXiv:1810.07816. Our improvement is based on new algorithmic techniques, and some of these may lead to advances on related problems.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset