We provide a $5/4$-approximation algorithm for the minimum 2-edge-connected spanning subgraph problem. This improves upon the previous best ratio of $4/3$. The algorithm is based on applying local improvement steps on a starting solution provided by a standard ear decomposition together with the idea of running several iterations on residual graphs by excluding certain edges that do not belong to an optimum solution. The latter idea is a novel one, which allows us to bypass $3$-ears with no loss in approximation ratio, the bottleneck for obtaining a performance guarantee below $3/2$. Our algorithm also implies a simpler $7/4$-approximation algorithm for the matching augmentation problem, which was recently treated.
翻译:我们为最小的两端连接的覆盖子图问题提供了5/4美元的接近算法。这比以前的最佳比率4/3美元有所改进。算法的基础是对标准耳分解提供的起始解决方案采用当地改良步骤,同时在残余图上运行若干迭代,排除某些不属于最佳解决办法的边缘。后一种想法是一个新颖的想法,使我们能够绕过3美元ears,而近似率没有亏损,这是获得3/2美元以下性能保证的瓶颈。我们的算法还意味着为匹配的扩增问题采用更简单的7/4美元的近似算法,这个问题最近得到了处理。