In this paper, we study the problem of finding a maximum matching in the semi-streaming model when edges arrive in random order. In the semi-streaming model, an algorithm receives a stream of edges and it is allowed to have a memory of $\tilde{O}(n)$ where $n$ is the number of vertices in the graph. A recent work shows that there exists a streaming algorithm with the approximation ratio of $\frac{2}{3}$ that uses $\tilde{O}(n^{1.5})$ memory. However, their memory is much larger than the memory constraint of the semi-streaming algorithms. In this work, we further investigate this problem in the semi-streaming model, and we give the first better-than-$0.5$ approximation algorithm in the semi-streaming model.
Our main results are as follow.
We show that there exists a single-pass deterministic semi-streaming algorithm that finds a $\frac{3}{5} (= 0.6)$ approximation of the maximum matching in bipartite graphs using $\tilde{O}(n)$ memory. This result outperforms the state-of-the-art result that finds a $0.539$ approximation of the maximum matching using $\tilde{O}(n)$ memory.
By giving a black-box reduction from finding a matching in general graphs to finding a matching in bipartite graphs, we show there exists a single-pass deterministic semi-streaming algorithm that finds a $\frac{6}{11} (\approx 0.545)$ approximation of the maximum matching in general graphs, improving upon the state-of-art result $0.506$ approximation. Our work is the first better-than-$0.5$ approximation algorithm for this problem in the semi-streaming model.