论文标题
击败sublerear时期的贪婪匹配
Beating Greedy Matching in Sublinear Time
论文作者
论文摘要
我们研究用于估计图中最大匹配的大小的均匀时间算法。我们的主要结果是$（\ frac {1} {2}+ω（1））$ - 近似算法，可以用$ o（n^{1+ε}）$时间实现，其中$ n $是顶点的数量，而常数$ε> 0 $可以任意地任意。对于该问题，最著名的下限是$ω（n）$，它适用于任何恒定近似。 现有算法要么获得$ \ frac {1} {2} $ - 近似[Behnezhad focs'21]的贪婪界限，要么需要在最大程度上进行一些假设才能以$ O（n^2）$ - time [Yoshida，Yamamoto，Yamamoto和Ito Stoc'09]运行。我们通过设计一种较少的“自适应”增强算法来改进这些方法，以最大程度地匹配可能具有独立的匹配。
We study sublinear time algorithms for estimating the size of maximum matching in graphs. Our main result is a $(\frac{1}{2}+Ω(1))$-approximation algorithm which can be implemented in $O(n^{1+ε})$ time, where $n$ is the number of vertices and the constant $ε> 0$ can be made arbitrarily small. The best known lower bound for the problem is $Ω(n)$, which holds for any constant approximation. Existing algorithms either obtain the greedy bound of $\frac{1}{2}$-approximation [Behnezhad FOCS'21], or require some assumption on the maximum degree to run in $o(n^2)$-time [Yoshida, Yamamoto, and Ito STOC'09]. We improve over these by designing a less "adaptive" augmentation algorithm for maximum matching that might be of independent interest.
