Semi-Streaming Bipartite Matching in Fewer Passes and Less Space
share
We provide algorithms with improved pass and space complexities for approximately solving linear programs, optimal transport, bipartite matching, and more in the semi-streaming model. For instance, we provide a (randomized) algorithm computing a maximum cardinality matching in an unweighted bipartite graph in O(log^2 n ·ϵ^-1) passes, using O(n log^2 n ·ϵ^-1) auxiliary memory. This marks the first improvements to the O(loglogϵ^-1·ϵ^-2) pass, O(n loglogϵ^-1·ϵ^-2)-space algorithms of [AG13] when ϵ is moderately small. To obtain our results, we give an O(n) space deterministic semi-streaming algorithm for approximating the value of linear programs (in the form of box-simplex games), based on low-space implementations of [She17, JST19]. We further give a general sampling procedure for explicitly forming a fractional solution in low space, yielding improved semi-streaming guarantees for optimal transport and, in some regimes, maximum weighted matching. Finally, we improve the space complexity of our maximum cardinality matching method using an implicit implementation of the random walk rounding of [GKK10] via custom turnstile samplers.
READ FULL TEXT