Approximate Maximum Matching in Random Streams
share
In this paper, we study the problem of finding a maximum matching in the semi-streaming model when edges arrive in a random order. In the semi-streaming model, an algorithm receives a stream of edges and it is allowed to have a memory of Õ(n) where n is the number of vertices in the graph. A recent inspiring work by Assadi et al. shows that there exists a streaming algorithm with the approximation ratio of 2/3 that uses Õ(n^1.5) memory. However, the memory of their algorithm 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 present simple algorithms for approximating maximum matching in the semi-streaming model. Our main results are as follows. We show that there exists a single-pass deterministic semi-streaming algorithm that finds a 3/5 (= 0.6) approximation of the maximum matching in bipartite graphs using Õ(n) memory. This result significantly outperforms the state-of-the-art result of Konrad that finds a 0.539 approximation of the maximum matching using Õ(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 6/11 (≈ 0.545) approximation of the maximum matching in general graphs, improving upon the state-of-art result 0.506 approximation by Gamlath et al.
READ FULL TEXT