
























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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。