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...)id="MJXp-Span-7">˜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 23 that uses ˜O(n1.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 35(=0.6) approximation of the maximum matching in bipartite graphs using ˜O(n) memory. This result outperforms the state-of-the-art result that finds a 0.539 approximation of the maximum matching using ˜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) 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.
@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},
}