Bamas, EtienneDrygala, MarinaSvensson, Ola2022-11-072022-11-072022-11-072022-01-0110.1007/978-3-031-06901-7_5https://infoscience.epfl.ch/handle/20.500.14299/191886WOS:000870458800005The Matching Augmentation Problem (MAP) has recently received significant attention as an important step towards better approximation algorithms for finding cheap 2-edge connected subgraphs. This has culminated in a 5/3-approximation algorithm. However, the algorithm and its analysis are fairly involved and do not compare against the problem's well-known LP relaxation called the cut LP.In this paper, we propose a simple algorithm that, guided by an optimal solution to the cut LP, first selects a DFS tree and then finds a solution to MAP by computing an optimum augmentation of this tree. Using properties of extreme point solutions, we show that our algorithm always returns (in polynomial time) a better than 2-approximation when compared to the cut LP. We thereby also obtain an improved upper bound on the integrality gap of this natural relaxation.Computer Science, Theory & MethodsMathematics, AppliedComputer ScienceMathematicstree augmentationgraphtext::conference output::conference proceedings::conference paper