论文标题
在更少的通行证和最佳空间中，半流式匹配
Semi-Streaming Bipartite Matching in Fewer Passes and Optimal Space
论文作者
论文摘要
我们提供$ \ widetilde {o}（ε^{ - 1}）$ - 通过双分段图中的$（1-ε）$计算$（1-ε）$的半流式算法。我们最有效的方法是确定性和最佳方法，$ o（n）$，空间，改善了先前最先进的$ \ widetilde {o}（ε^{ - 1}）$ - 通过AHN和GUHA的算法。为了获得我们的结果，我们提供了更通用的连续优化工具的半流改编。此外，我们利用这些技术来获得近似线性编程，最佳传输，精确匹配，转移和最短路径问题的流式变体的改进。
We provide $\widetilde{O}(ε^{-1})$-pass semi-streaming algorithms for computing $(1-ε)$-approximate maximum cardinality matchings in bipartite graphs. Our most efficient methods are deterministic and use optimal, $O(n)$, space, improving upon the space complexity of the previous state-of-the-art $\widetilde{O}(ε^{-1})$-pass algorithm of Ahn and Guha. To obtain our results we provide semi-streaming adaptations of more general continuous optimization tools. Further, we leverage these techniques to obtain improvements for streaming variants of approximate linear programming, optimal transport, exact matching, transshipment, and shortest path problems.
