  The 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
$\frac{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.
