论文标题
一个简单的基于LP的近似算法，用于匹配增强问题
A Simple LP-Based Approximation Algorithm for the Matching Augmentation Problem
论文作者
论文摘要
匹配的增强问题（MAP）最近受到了极大的关注，这是朝着更好近似算法寻找便宜$ 2 $ - 边缘连接子图的重要一步。这已经达到了$ \ frac {5} {3} $ - 近似算法。但是，该算法及其分析是相当涉及的，并且没有与该问题众所周知的LP松弛相比，称为CUT LP。在本文中，我们提出了一种简单的算法，该算法以最佳的解决方案为指导，首先选择DFS树，然后通过计算该树的最佳增强来找到映射的解决方案。使用Extreme Point解决方案的属性，我们表明我们的算法始终（以多项式时间）返回（在多项式时间内），与CUT LP相比，算法的算法大于2美元。因此，我们还获得了这种自然放松的整体差距的改进的上限。
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.
