论文标题
在动态流中最大匹配的渐近最佳算法
An Asymptotically Optimal Algorithm for Maximum Matching in Dynamic Streams
论文作者
论文摘要
我们提出了一种算法，该算法在具有 *渐变性最佳 *空间复杂性的动态（插入消耗）流中最大匹配问题：对于任何$ n $ vertex Graph，我们具有较高概率的算法，我们具有较高概率的算法将使用$ O（N^2/α^3）$ bits $ o（$α$ approxigation）在单个Pass中进行$α$ -AppRoxigate匹配。 在动态流匹配问题上进行的一长串工作已将空间上限和下限之间的差距缩小到$ n^{o（1）} $ castor [assadi-khanna-li-yaroslavtsev; Soda 2016]，然后是$ \ text {polylog} {（n）} $因子[dark-konrad; CCC 2020]。现在，我们的上限与Dark-Konrad的下部界限匹配到$ O（1）$因素，从而完成了这一方向。 我们的方法包括两个主要步骤：我们首先（证明是）确定了一个图形系列，类似于以前工作中用于建立该问题的下限的实例，这是唯一关注的“难”实例。这些图包括一个诱导的子图，既稀疏又包含较大的匹配。然后，我们为这个图形系列设计了一种动态流算法，该算法比先前的工作更有效。这种效率的关键是一种新颖的草图方法，它绕过了$ \ text {polylog} {（n）} $ - 太空因素的典型损失，而与标准$ l_0 $ - 缩采样原始基原始人相比，可以独立于设计其他流媒体问题的最佳算法。
We present an algorithm for the maximum matching problem in dynamic (insertion-deletions) streams with *asymptotically optimal* space complexity: for any $n$-vertex graph, our algorithm with high probability outputs an $α$-approximate matching in a single pass using $O(n^2/α^3)$ bits of space. A long line of work on the dynamic streaming matching problem has reduced the gap between space upper and lower bounds first to $n^{o(1)}$ factors [Assadi-Khanna-Li-Yaroslavtsev; SODA 2016] and subsequently to $\text{polylog}{(n)}$ factors [Dark-Konrad; CCC 2020]. Our upper bound now matches the Dark-Konrad lower bound up to $O(1)$ factors, thus completing this research direction. Our approach consists of two main steps: we first (provably) identify a family of graphs, similar to the instances used in prior work to establish the lower bounds for this problem, as the only "hard" instances to focus on. These graphs include an induced subgraph which is both sparse and contains a large matching. We then design a dynamic streaming algorithm for this family of graphs which is more efficient than prior work. The key to this efficiency is a novel sketching method, which bypasses the typical loss of $\text{polylog}{(n)}$-factors in space compared to standard $L_0$-sampling primitives, and can be of independent interest in designing optimal algorithms for other streaming problems.
