论文标题
与几个查询的随机匹配：$（1- \ varepsilon）$近似
Stochastic Matching with Few Queries: $(1-\varepsilon)$ Approximation
论文作者
论文摘要
假设我们给我们一个任意图$ g =（v，e）$，并且知道$ e $中的每个边缘都将通过某些概率$ p $独立实现。随机匹配问题的目标是选择$ g $的稀疏子图$ q $ q $，以便以$ q $为预期的已实现的边缘包括一个匹配，大约与$ g $的实现边缘之间的最大匹配度大约大。 $ Q $的最高度可以取决于$ p $，但不取决于$ g $。 多年来，这个问题一直在进行大量研究，近似因素已从$ 0.5 $提高到0.5001美元，至$ 0.6568 $，最终提高到$ 2/3 $。在这项工作中，我们分析了一种基于天然抽样的算法，并表明它可以将其一路达到$（1-ε）$近似，对于任何常数$ε> 0 $。 我们分析的键和可能的独立兴趣部分是一种算法，该算法在随机图上构造匹配，在其他重要属性中，保证每个顶点与足够远的顶点独立于匹配。这使我们能够绕过以前已知的障碍，以实现基于密集的Ruzsa-Szemerédi图的存在。
Suppose that we are given an arbitrary graph $G=(V, E)$ and know that each edge in $E$ is going to be realized independently with some probability $p$. The goal in the stochastic matching problem is to pick a sparse subgraph $Q$ of $G$ such that the realized edges in $Q$, in expectation, include a matching that is approximately as large as the maximum matching among the realized edges of $G$. The maximum degree of $Q$ can depend on $p$, but not on the size of $G$. This problem has been subject to extensive studies over the years and the approximation factor has been improved from $0.5$ to $0.5001$ to $0.6568$ and eventually to $2/3$. In this work, we analyze a natural sampling-based algorithm and show that it can obtain all the way up to $(1-ε)$ approximation, for any constant $ε> 0$. A key and of possible independent interest component of our analysis is an algorithm that constructs a matching on a stochastic graph, which among some other important properties, guarantees that each vertex is matched independently from the vertices that are sufficiently far. This allows us to bypass a previously known barrier towards achieving $(1-ε)$ approximation based on existence of dense Ruzsa-Szemerédi graphs.
