Finding Matchings in the Streaming Model
Andrew McGregor · 2004
This report presents algorithms for finding large matchings in the streaming model. In this model, applicable when dealing with massive graphs, edges are streamed-in in some arbitrary order rather than residing in randomly accessible memory. For ε> 0, we achieve a 1/(1+ε) approximation for maximum cardinality matching and a 1/(2+ε) approximation to maximum weighted matching. Both algorithms use a constant number of passes.