Beating Two-Thirds For Random-Order Streaming Matching

Authors: Sepehr Assadi, Soheil Behnezhad
Conference: The 48th International Colloquium on Automata, Languages and Programming (ICALP 2021)
Abstract: We study the maximum matching problem in the random-order semi-streaming setting. In this problem, the edges of an arbitrary n-vertex graph G=(V,E) arrive in a stream one by one and in a random order. The goal is to have a single pass over the stream, use n⋅poly(logn) space, and output a large matching of G.

We prove that for an absolute constant ϵ0 > 0, one can find a (2/3+ϵ0)-approximate maximum matching of G using O(nlogn) space with high probability. This breaks the natural boundary of 2/3 for this problem prevalent in the prior work and resolves an open problem of Bernstein [ICALP'20] on whether a (2/3+Ω(1))-approximation is achievable.
Full version: [arXiv]
Streaming Video: [YouTube] (Soheil's presentation at IRF)