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.
翻译:匹配增强问题(MAP)最近作为寻找廉价的$2美元顶端连接子谱的更近似算法的重要一步,引起了人们的极大关注。 这最终形成了一个$\frac{5 ⁇ 3}$occeration 算法。 然而,算法及其分析是公平的,没有与问题众所周知的LP松绑(即削减的LP)相比较。 在本文中,我们提出了一个简单的算法,在削减的LP最佳解决方案的指导下,首先选择了FFFS树,然后通过计算这棵树的最佳增益来找到对MAP的解决方案。我们使用极端点解决方案的特性,表明我们的算法总是(在多点时间)比削减的LP还好,比2美元相近。 因此,我们在这种自然放松的整体差距上也得到了改进。