论文标题
$（1.5+ε）$ - 近似匹配的sublinear算法
Sublinear Algorithms for $(1.5+ε)$-Approximate Matching
论文作者
论文摘要
我们研究了用于估计最大匹配大小的均匀时间算法。经过长期的研究，贝内扎德（Behnezhad）[focs'22]最终解决了这个问题，该政权愿意支付约2美元的近似值。最近，Behnezhad等人[SODA'23]使用$ n^{1+γ} $ time，将近似因子提高到$（2- \ frac {1} {2^{o（1/γ}}）$。但是，对因子$ 2 $的这种改善是微不足道的，他们询问甚至在$ n^{2-Ω（1）} $时间中是否可以使用$ 1.99 $ - APPRXIMATION。我们通过显示$（1.5+ε）$ - 以$ n^{2-θ（ε^{2}} $ time运行的$（1.5+ε）$ - 近似算法，我们给出了强烈的肯定答案。我们的方法在概念上很简单，并且与以前所有均匀的时间匹配算法有所不同：我们显示了一种用于计算边缘数度约束子图（EDCS）变体的sublinear时间算法，该概念以前在动态方面利用了这种概念[Bernstein Stein stein stein stein iallp'15，Soda'16]，分布式[Assadi [assadi et assadi et assadi et ansadi et ansadi et ansadi。 Soda'19]和流[Bernstein iCalp'20]设置，但在sublinear设置中从来没有。独立工作：Behnezhad，Roghani和Rubinstein [BRR'23]独立地显示了sublinear算法在邻接列表和矩阵模型中类似于我们的定理1.2。此外，在[BRR'23]中，它们在上层和下边界的近似匹配算法上严格比1.5近似匹配的算法显示了其他结果。
We study sublinear time algorithms for estimating the size of maximum matching. After a long line of research, the problem was finally settled by Behnezhad [FOCS'22], in the regime where one is willing to pay an approximation factor of $2$. Very recently, Behnezhad et al.[SODA'23] improved the approximation factor to $(2-\frac{1}{2^{O(1/γ)}})$ using $n^{1+γ}$ time. This improvement over the factor $2$ is, however, minuscule and they asked if even $1.99$-approximation is possible in $n^{2-Ω(1)}$ time. We give a strong affirmative answer to this open problem by showing $(1.5+ε)$-approximation algorithms that run in $n^{2-Θ(ε^{2})}$ time. Our approach is conceptually simple and diverges from all previous sublinear-time matching algorithms: we show a sublinear time algorithm for computing a variant of the edge-degree constrained subgraph (EDCS), a concept that has previously been exploited in dynamic [Bernstein Stein ICALP'15, SODA'16], distributed [Assadi et al. SODA'19] and streaming [Bernstein ICALP'20] settings, but never before in the sublinear setting. Independent work: Behnezhad, Roghani and Rubinstein [BRR'23] independently showed sublinear algorithms similar to our Theorem 1.2 in both adjacency list and matrix models. Furthermore, in [BRR'23], they show additional results on strictly better-than-1.5 approximate matching algorithms in both upper and lower bound sides.
