Space Lower Bounds for Approximating Maximum Matching in the Edge Arrival Model
Space Lower Bounds for Approximating Maximum Matching in the Edge Arrival Model
复制标题
边缘到达模型中近似最大匹配的空间下界
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
M. Kapralov
中科院分区：
文献类型：
--
作者：
M. Kapralov
最近，在线和流设置中的双方匹配问题最近引起了很多关注。著名的Karp，Vazirani和Vazirani（KVV）算法实现了$ 1-1/e $ $近似的经典顶点到达设置，这在线和半决赛中都是最佳的。 - 流程设置，其中算法被限制为使用$ n \ cdot \ log^{o（1）} n $ 空间。在线算法文献中，边缘到达模型越具有挑战性的到来模型取得了重大进展。对于严格的在线模型（没有先发制人）的近似值比琐碎因子$ 1/2 $更好[Gamlath et al'focs'19]。对于限制性较小的在线抢先模型，一个比$ \ frac1 {1+ \ ln 2} $ - 近似[Epstein et al'Stacs'12]，甚至比$（2- \ sqrt {2}）$更好[Huang et al'Soda'19]被排除在外。边缘到达模型中在线抢先匹配的最新硬度结果是基于使用Edge Arrivals将KVV硬实例的多个副本串在一起的想法。在本文中，我们展示了如何使用有关Ruzsa-Szemer \'edi图的文献中开发的思想实施此类构造。结果，我们表明，任何单个通过流算法都在两分图中近似于$ n $顶点的最大匹配，比$ \ frac1 {1+ \ ln 2} \ oft $ n $ vertices更好。 1+ \ Omega（1/\ log \ log n）} \ gg n \ log^{o（1）} n $ space。这给出了经典的单面顶点到达设置与半流模型中的边缘到达设置之间的第一个分离。
The bipartite matching problem in the online and streaming settings has received a lot of attention recently. The classical vertex arrival setting, for which the celebrated Karp, Vazirani and Vazirani (KVV) algorithm achieves a $1-1/e$ approximation, is rather well understood: the $1-1/e$ approximation is optimal in both the online and semi-streaming setting, where the algorithm is constrained to use $n\cdot \log^{O(1)} n$ space. The more challenging the edge arrival model has seen significant progress recently in the online algorithms literature. For the strictly online model (no preemption) approximations better than trivial factor $1/2$ have been ruled out [Gamlath et al'FOCS'19]. For the less restrictive online preemptive model a better than $\frac1{1+\ln 2}$-approximation [Epstein et al'STACS'12] and even a better than $(2-\sqrt{2})$-approximation[Huang et al'SODA'19] have been ruled out. The recent hardness results for online preemptive matching in the edge arrival model are based on the idea of stringing together multiple copies of a KVV hard instance using edge arrivals. In this paper, we show how to implement such constructions using ideas developed in the literature on Ruzsa-Szemer\'edi graphs. As a result, we show that any single pass streaming algorithm that approximates the maximum matching in a bipartite graph with $n$ vertices to a factor better than $\frac1{1+\ln 2}\approx 0.59$ requires $n^{1+\Omega(1/\log\log n)}\gg n \log^{O(1)} n$ space. This gives the first separation between the classical one sided vertex arrival setting and the edge arrival setting in the semi-streaming model.