论文标题
简单的1-1/e近似，用于遗忘的两部分匹配
A Simple 1-1/e Approximation for Oblivious Bipartite Matching
论文作者
论文摘要
我们研究了遗忘的匹配问题，该问题旨在在未知边集的图表上找到最大匹配。该问题的任何算法都指定了顶点对的排序。然后，通过在订购后探测对来产生匹配，如果两个对都无与伦比，则包括一对，并且之间存在边缘。精心研究了该问题的未加权（Chan等人（Sicomp 2018））和顶点加权（Chan等人（Talg 2018））。 在本文中，我们考虑了两分图上的边缘加权遗漏匹配问题，该问题概括了随机的两部分匹配问题。最近，Gamlath等人。 （SODA 2019）研究了随机的两分匹配问题，并提出了（1-1/e） - 同一算法。我们提供了一种非常简单的算法，该算法根据Karp等人的排名算法进行了改编。 （STOC 1990），并表明它在两部分图上忽略的匹配问题达到了相同的（1-1/e）近似值。
We study the oblivious matching problem, which aims at finding a maximum matching on a graph with unknown edge set. Any algorithm for the problem specifies an ordering of the vertex pairs. The matching is then produced by probing the pairs following the ordering, and including a pair if both of them are unmatched and there exists an edge between them. The unweighted (Chan et al. (SICOMP 2018)) and the vertex-weighted (Chan et al. (TALG 2018)) versions of the problem are well studied. In this paper, we consider the edge-weighted oblivious matching problem on bipartite graphs, which generalizes the stochastic bipartite matching problem. Very recently, Gamlath et al. (SODA 2019) studied the stochastic bipartite matching problem, and proposed an (1-1/e)-approximate algorithm. We give a very simple algorithm adapted from the Ranking algorithm by Karp et al. (STOC 1990), and show that it achieves the same (1-1/e) approximation ratio for the oblivious matching problem on bipartite graph.
