论文标题
司额时间算法和近似最大匹配的复杂性
Sublinear Time Algorithms and Complexity of Approximate Maximum Matching
论文作者
论文摘要
长期以来一直研究了用于近似最大匹配大小的均值时间算法。在过去的二十年中，关于这个问题的大部分进展一直在算法方面。例如，behnezhad [focs'21]的算法在$ \ tilde {o}（n）$ time of $ n $ vertex图中获得了1/2- approximation。 Behnezhad，Roghani，Rubinstein和Saberi [Soda'23]的最新算法在$ O（n^{1+ε}）$时间中获得了比1/2的近似值。在下边界，Parnas和Ron [TCS'07]在15年前表明，获得最大匹配大小的任何恒定近似都需要$ω（n）$时间。从那以后，即使以$（1-ε）$近似，也证明了$ n $下限中的任何超级线性，即 在本文中，我们证明了此问题的第一个超级线性。我们表明，在获得$（\ frac {2} {3} {3} +ω（1））$最大匹配大小的近似值时，至少需要$ n^{1.2 -o（1）} $查询模型。即使该图是二分，也可以保证具有$θ（n）$的匹配。我们的下限论点是建立在相关衰减等技术的基础上的，据我们所知，在证明sublrinear时间下限之前尚未使用。 我们通过提出两种在$ n^{2-ω（1）} $的强烈倍率时间内运行的算法来补充下限。第一种算法实现了$（\ frac {2} {3}-ε）$ - 近似；这显着改善了先前的近1/2近似值。我们的第二个算法获得了$（\ frac {2} {3} {3}+ω（1））$的更好近似因子。这打破了普遍的$ 2/3 $ - approximation屏障，重要的是表明，我们的$ n^{1.2-o（1）} $ time下限制$（\ frac {2} {3} {3}+ω（1））$ - 近似值不能一路提高到$ n^{2-o（1）$。
Sublinear time algorithms for approximating maximum matching size have long been studied. Much of the progress over the last two decades on this problem has been on the algorithmic side. For instance, an algorithm of Behnezhad [FOCS'21] obtains a 1/2-approximation in $\tilde{O}(n)$ time for $n$-vertex graphs. A more recent algorithm by Behnezhad, Roghani, Rubinstein, and Saberi [SODA'23] obtains a slightly-better-than-1/2 approximation in $O(n^{1+ε})$ time. On the lower bound side, Parnas and Ron [TCS'07] showed 15 years ago that obtaining any constant approximation of maximum matching size requires $Ω(n)$ time. Proving any super-linear in $n$ lower bound, even for $(1-ε)$-approximations, has remained elusive since then. In this paper, we prove the first super-linear in $n$ lower bound for this problem. We show that at least $n^{1.2 - o(1)}$ queries in the adjacency list model are needed for obtaining a $(\frac{2}{3} + Ω(1))$-approximation of maximum matching size. This holds even if the graph is bipartite and is promised to have a matching of size $Θ(n)$. Our lower bound argument builds on techniques such as correlation decay that to our knowledge have not been used before in proving sublinear time lower bounds. We complement our lower bound by presenting two algorithms that run in strongly sublinear time of $n^{2-Ω(1)}$. The first algorithm achieves a $(\frac{2}{3}-ε)$-approximation; this significantly improves prior close-to-1/2 approximations. Our second algorithm obtains an even better approximation factor of $(\frac{2}{3}+Ω(1))$ for bipartite graphs. This breaks the prevalent $2/3$-approximation barrier and importantly shows that our $n^{1.2-o(1)}$ time lower bound for $(\frac{2}{3}+Ω(1))$-approximations cannot be improved all the way to $n^{2-o(1)}$.
