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.
翻译：我们为匹配扩增问题(MAP)提出了一个$\frac53$-准协调算法:考虑到成本边缘为零或一等的多重算法,成本边缘为零形成匹配,找到一个最低成本的两端连接的子谱(2-ECSS),最近提出了同一问题的一个$frac74$-准协调算法,见Cheriyan等人,“匹配增强算法:一个$frac{7>4}$-准协调算法”, {em Math. program.}, 182(1):315-354, 2020;arXiv:180.07816。我们的改进是基于新的算法,其中一些改进可能导致相关问题的进展。
相关内容
微信扫码咨询专知VIP会员