An Auction Algorithm for Bipartite Matching in Streaming and Massively Parallel Computation Models

A general class of algorithms for the bipartite matching problem are “auction algorithms”. These algorithms interpret the input bipartite graph as a collection of bidders on one side and items on the other side, and hold an auction for finding a welfare-maximizing assignment of items to bidders which translates to a maximum matching of the input graph. We design a simple and generic auction algorithm that reduces the problem of finding a (1 − ε)-approximate bipartite matching to that of finding O(1/ε²) maximal matchings in adaptively chosen subgraphs of the input. Despite its simplicity, this technique gives a powerful tool for boosting approximation ratio of algorithms for the bipartite matching problem from the 2-approximation of maximal matching to (1 − ε)-approximation in different settings. For instance, we obtain the following algorithms for the bipartite matching problem as a corollary: • A deterministic O(1/ε²)-pass O(n)-space algorithm in the graph streaming model; this improves the pass complexity of the state-of-the-art algorithms by O(log log(1/ε)) and the space complexity by O(1/ε) to achieve optimal space bounds with no dependence on ε. • A randomized O(1/ε² · log log n)-round O(n) memory algorithm in the Massively Parallel Computation (MPC) model; the round-complexity of the algorithm improves upon the state-of-the-art by an (1/ε)^O(1/ε) factor while maintaining the same memory per machine.