Conference
Alireza Farhadi, MohammadTaghi Hajiaghayi, Tung Mai, Anup Rao, Ryan A. Rossi.

Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Pages 1-20, 2020.

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 (More...)class="mjx-chtml MathJax_CHTML" tabindex="0" data-mathml="$\stackrel{\#x007E;}{O}\left(n\right)$" role="presentation" style="font-size: 117%; position: relative;">~O(n)$\stackrel{~}{O}(n)$ where n$n$ is the number of vertices in the graph. A recent work shows that there exists a streaming algorithm with the approximation ratio of 23$\frac{2}{3}$ that uses ~O(n1.5)$\stackrel{~}{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$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 35(=0.6)$\frac{3}{5}(=0.6)$ approximation of the maximum matching in bipartite graphs using ~O(n)$\stackrel{~}{O}(n)$ memory. This result outperforms the state-of-the-art result that finds a 0.539$0.539$ approximation of the maximum matching using ~O(n)$\stackrel{~}{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 611(≈0.545)$\frac{6}{11}(\approx 0.545)$ approximation of the maximum matching in general graphs, improving upon the state-of-art result 0.506$0.506$ approximation. Our work is the first better-than-0.5$0.5$ approximation algorithm for this problem in the semi-streaming model.

@inproceedings{farhadi2020stream-matching,
author={Alireza Farhadi and MohammadTaghi Hajiaghayi and Tung Mai and Anup Rao and Ryan A. Rossi},
title={Approximate Maximum Matching in Random Streams},
booktitle={Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
year={2020},
pages={1-20},
}