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 ⅔ 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 and clean 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 approximation of the maximum matching in bipartite graphs using Õ ( n ) memory. This result significantly outperforms the state-of-the-art result of Konrad [12] 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 (≈ 0. 545) approximation of the maximum matching in general graphs, improving upon the state-of-art result 0. 506 approximation by Gamlath et al. [8].

Authors

• Alireza Farhadi 0001
• MohammadTaghi Hajiaghayi
• Tung Mai
• Anup B. Rao
• Ryan A. Rossi

Keywords

No keywords are indexed for this paper.