关于无意识匹配问题

作者：Zhihao Gavin Tang,Xiaowei Wu,Yuhao Zhang

摘要：关于无意识匹配问题的扰动扩散我们研究了不经意设置中的最大匹配问题，即该算法未知图的边集。在这对顶点的探针上显示出边缘的存在。此外，如果在两个探测顶点之间存在边缘，则边缘必须不可撤销地包括在匹配中。对于未加权图，Karp等人的术语{rankingf {Ranking}算法〜（STOC 1990）实现了二分图的近似比率为0.96，而对于一般图表则为0.526。对于顶点加权图，Chan等。 （TALG 2018）提出了a0.501近似算法。相比之下，边缘加权版本只承认Greedy的琐碎0.5近似值。

在本文中，我们提出了\ textsf {Perturbed Greedy}算法用于边缘加权遗忘匹配问题，并证明它达到了0.501的近似比率。此外，我们证明了我们的算法在非加权图上的近似比对于二分图是0.639，对于一般图是0.531。后者改进了Chan等人的最新结果。 （TALG 2018）。此外，我们的算法可以被视为\ textsf {Modified Randomized Greedy}（MRG）算法的健壮版本。通过暗示，我们的0.531近似比率作为MRG算法超出（1/2 +ε）范围的第一个分析。

原文标题：Perturbed Greedy on Oblivious Matching Problems

原文摘要：We study the maximum matching problem in the oblivious setting, i.e. the edge set of the graph is unknown to the algorithm. The existence of an edge is revealed upon the probe of this pair of vertices. Further, if an edge exists between two probed vertices, then the edge must be included in the matching irrevocably. For unweighted graphs, the \textsf{Ranking} algorithm by Karp et al.~(STOC 1990) achieves approximation ratios0.696for bipartite graphs and0.526for general graphs. For vertex-weighted graphs, Chan et al. (TALG 2018) proposed a0.501-approximate algorithm. In contrast, the edge-weighted version only admits the trivial0.5-approximation by Greedy.

In this paper, we propose the \textsf{Perturbed Greedy} algorithm for the edge-weighted oblivious matching problem and prove that it achieves a0.501approximation ratio. Besides, we show that the approximation ratio of our algorithm on unweighted graphs is0.639for bipartite graphs, and0.531for general graphs. The later improves the state-of-the-art result by Chan et al. (TALG 2018). Furthermore, our algorithm can be regarded as a robust version of the \textsf{Modified Randomized Greedy} (MRG) algorithm. By implication, our0.531approximation ratio serves as the first analysis of the MRG algorithm beyond the(1/2+ϵ)regime.

地址：https://arxiv.org/abs/1907.05135