On Regularity Lemma and Barriers in Streaming and Dynamic Matching
On Regularity Lemma and Barriers in Streaming and Dynamic Matching
复制标题
流媒体和动态匹配中的正则引理和障碍
DOI：
10.1145/3564246.3585110
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Li, Huan
中科院分区：
文献类型：
--
作者：
Assadi, Sepehr;Behnezhad, Soheil;Khanna, Sanjeev;Li, Huan
我们基于 Szemerédi 著名的正则引理，提出了一种在密集图中查找匹配的新方法。这使我们能够在流图和动态图中的匹配的长期界限上获得不平凡的改进，尽管略有改进。特别是，我们为 n 顶点图建立了以下结果：一种确定性单通道流算法，可找到 (1−o(1)) 近似匹配 ino(n2) 位的空间。这是次线性空间中针对此问题的第一个单遍算法，该算法比贪婪算法的 1/2 近似有所改进。一种随机动态算法，它以高概率维持每个边缘插入或删除的 (1−o(1)) 近似匹配 ino(n) 最坏情况更新时间。该算法甚至可以对抗自适应对手。这是第一个 (n) 更新时间动态算法，其近似保证任意接近于 1。考虑到正则性引理的使用，我们的算法在微不足道的范围上获得的改进仅是某个 (log*n)θ(1) 因子。然而，在每种情况下，它们都表明问题的“正确”答案并不是由先前的界限决定的。最后，在流模型中，我们还提出了一种随机 (1−o(1)) 近似算法，其空间可以由某些 Ruzsa-Szemerédi (RS) 图的密度上限。虽然 RS 图现在已被广泛用于证明流下界，但我们是第一个将它们用作设计改进流算法的上限工具。
We present a new approach for finding matchings in dense graphs by building on Szemerédi’s celebrated Regularity Lemma. This allows us to obtain non-trivial albeit slight improvements over longstanding bounds for matchings in streaming and dynamic graphs. In particular, we establish the following results forn-vertex graphs:A deterministicsingle-pass streamingalgorithm that finds a (1−o(1))-approximate matching ino(n2) bits of space. This constitutes the first single-pass algorithm for this problem in sublinear space that improves over the 1/2-approximation of the greedy algorithm.A randomizedfully dynamicalgorithm that with high probability maintains a (1−o(1))-approximate matching ino(n) worst-case update time per each edge insertion or deletion. The algorithm works even against an adaptive adversary. This is the firsto(n) update-time dynamic algorithm with approximation guarantee arbitrarily close to one.Given the use of regularity lemma, the improvement obtained by our algorithms over trivial bounds is only by some (log*n)Θ(1)factor. Nevertheless, in each case, they show that the “right” answer to the problem is not what is dictated by the previous bounds.Finally, in the streaming model, we also present a randomized (1−o(1))-approximation algorithm whose space can be upper bounded by the density of certain Ruzsa-Szemerédi (RS) graphs. While RS graphs by now have been used extensively to prove streaming lower bounds, ours is the first to use them as an upper bound tool for desigining improved streaming algorithms.
登录
查看更多内容
图形流上两次、三次以及更多次的最大匹配
DOI：
10.4230/lipics.approx-random.2017.15
发表时间：
2017
期刊：
and Combinatorial Optimization. Algorithms and Techniques
影响因子：
--
作者：
Kale, Sagar;Tirodkar, Sumedh
通讯作者：
Tirodkar, Sumedh
DOI：
10.4230/lipics.approx/random.2021.19
发表时间：
2021
期刊：
ArXiv
影响因子：
--
作者：
C. Konrad;Kheeran K. Naidu
通讯作者：
Kheeran K. Naidu
DOI：
10.1109/focs46700.2020.00040
发表时间：
2020
期刊：
2020
影响因子：
--
作者：
Assadi, Sepehr;Raz, Ran
通讯作者：
Raz, Ran
顶点覆盖的全动态维护
DOI：
10.1007/3-540-57899-4_44
发表时间：
1993
期刊：
ArXiv
影响因子：
--
作者：
Z. Ivkovic;E. Lloyd
通讯作者：
E. Lloyd
在一般图中维护 EDCS：更简单、密度敏感且具有最坏情况时间范围
DOI：
10.1137/1.9781611977066.2
发表时间：
2021
期刊：
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
F. Grandoni;Chris Schwiegelshohn;Shay Solomon;Amitai Uzrad
通讯作者：
Amitai Uzrad