We provide $\widetilde{O}(\epsilon^{-1})$-pass semi-streaming algorithms for computing $(1-\epsilon)$-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}(\epsilon^{-1})$-pass algorithm of Ahn and Gupta. 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, and exact matching.
翻译：我们提供$\全局性{O}(\\ allislon}-1}(\\ epsilon}-1})$pass 半流算法,用于计算(1-\ epsilon)$- $- 近似最大基点匹配的双面图形。我们最有效的方法是确定性并使用最佳的,$(n)$(n)$(o)$(o),空间,改进Ahn和Gupta以往最先进的全局性($\ loon}(\\\\\\ ilon}-1})$(massilon) $- passion 运算法的空间复杂性。为了获得我们的成果,我们提供更普遍的连续优化工具的半流适应性。此外,我们利用这些技术来改进近似线性编程、最优化和精确匹配的流变。
相关内容
微信扫码咨询专知VIP会员