论文标题
用于匹配增强问题的改进的近似算法
An Improved Approximation Algorithm for the Matching Augmentation Problem
论文作者
论文摘要
我们提出了$ \ frac53 $ - approximation算法，用于匹配增强问题（地图）：给定具有零或一个成本边缘的多画像，以使成本零的边缘形成匹配的边缘，找到一个2-边缘连接的跨度连接子级别（2- ecs）的最低成本。 最近提出了同一问题的$ \ frac74 $ - 附件算法，请参见Cheriyan等人，“匹配的增强问题：$ \ frac {7} {4} {4} $ - 近似算法，” {\ em Math。程序。}，182（1）：315--354，2020; Arxiv：1810.07816。 我们的改进是基于新的算法技术，其中一些可能导致有关相关问题的进展。
We present a $\frac53$-approximation algorithm for the matching augmentation problem (MAP): given a multi-graph with edges of cost either zero or one such that the edges of cost zero form a matching, find a 2-edge connected spanning subgraph (2-ECSS) of minimum cost. A $\frac74$-approximation algorithm for the same problem was presented recently, see Cheriyan, et al., "The matching augmentation problem: a $\frac{7}{4}$-approximation algorithm," {\em Math. Program.}, 182(1):315--354, 2020; arXiv:1810.07816. Our improvement is based on new algorithmic techniques, and some of these may lead to advances on related problems.
