Approximate Maximum Matching in Random Streams

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) 1 where n is the number of vertices in the graph. A recent inspiring work by Assadi et al. [1] 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 [15] 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 semistreaming 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. [9].