An Auction Algorithm for Bipartite Matching in Streaming and Massively Parallel Computation Models
Sepehr Assadi, S. Cliff Liu, Robert Endre Tarjan · Society for Industrial and Applied Mathematics eBooks · 2021
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/∊2) 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/∊2)-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/∊2 · 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.