2020/07/22 by J. Cheriyan, R. Cummings, Cheriyan, J. +5
Computer Science · #05C85 #68R10 #68W25 #90C27 #90C59 #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.DM #cs.DS #msc:05C85 #msc:68R10 #msc:68W25 #msc:90C27 #msc:90C59
paper · pdf · doi:10.48550/arxiv.2007.11559
30 pages, 6 figures
arxiv created 2020/12/11 · arxiv updated 2020/12/14
We present a \frac53-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 \frac74-approximation algorithm for the same problem was presented recently, see Cheriyan, et al., "The matching augmentation problem: a (7)/(4)-approximation algorithm," \em 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.