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

Authors: Sepehr Assadi, Cliff Liu, Robert E. Tarjan
Conference: The SIAM Symposium on Simplicity in Algorithms (SOSA@SODA'21)
Abstract: 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 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 (1/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.
Conference version: [PDF]