Maximum Matching in the Semi-Streaming Model in Constant Number of Passes

We consider the maximum matching problem in the semi-streaming model formalized by Feigenbaum et al. that is inspired by giant graphs of today.  The input is a stream of edges, and an algorithm can use a memory of O(n\poly\log n) to output a maximum matching. If an algorithm goes over the stream k times, then it is called a k pass algorithm. Maximal matching algorithm is a 2-approximation one-pass algorithm, and a big open problem is to find an algorithm which does better in one-pass.

We begin by giving a two-pass (1/2 + 1/16)-approximation algorithm for triangle-free graphs and a two-pass (1/2 + 1/32)-approximation algorithm for general graphs; these improve the approximation ratios of 1/2 + 1/52 for bipartite graphs and 1/2 + 1/140 for general graphs by Konrad, Magniez, and Mathieu.  In three passes, we achieve approximation ratios of 1/2 + 1/10 for triangle-free graphs and 1/2 + 1/19.753 for general graphs.  We also give a multi-pass algorithm where we bound the number of passes precisely---we give a (2/3 -\epsilon)-approximation algorithm that uses 2/(3\epsilon) passes for triangle-free graphs and 4/(3\epsilon) passes for general graphs.  Our algorithms are simple and combinatorial, use O(n \log(n)) space, and have O(1) update time per edge.

We extend the multipass algorithm to give a (3/4-\epsilon)-approximation algorithm that uses O(\log(1/\epsilon)/\epsilon) passes. This algorithm gives ideas for an (1-\epsilon)-approximation deterministic algorithm. Note that there is no known deterministic algorithm for general graphs which achieves (1-\epsilon)-approximation in constant number of passes.