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 O(n polylog n ) space, and output a large matching of G. We prove that for an absolute constant \epsilon_0 > 0, one can find a (2/3 + \epsilon_0)-approximate maximum matching of G using O(n \log n) 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 + \Omega(1))-approximation is achievable.
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 \cdot poly(\log n ) space, and output a large matching of G. We prove that for an absolute constant \epsilon_0 > 0, one can find a (2/3 + \epsilon_0)-approximate maximum matching of G using O(n \log n) 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 + \Omega(1))-approximation is achievable.
R
O(n polylog n
n \cdot poly(\log n
D
~