An Auction Algorithm for Bipartite Matching in Streaming and Massively Parallel Computation Models
Authors:
Sepehr Assadi, Cliff Liu, Robert E. Tarjan
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:
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]
BibTex:
[DBLP]