@inproceedings{b690431cf61c483caf4b1873795a8b23,

title = "An Auction Algorithm for Bipartite Matching in Streaming and Massively Parallel Computation Models",

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 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.",

author = "Sepehr Assadi and Liu, {S. Cliff} and Tarjan, {Robert E.}",

note = "Publisher Copyright: Copyright {\textcopyright} 2021 by SIAM.; 4th Symposium on Simplicity in Algorithms, SOSA 2021, co-located with SODA 2021 ; Conference date: 11-01-2021 Through 12-01-2021",

year = "2021",

language = "English (US)",

series = "4th Symposium on Simplicity in Algorithms, SOSA 2021",

publisher = "Society for Industrial and Applied Mathematics Publications",

pages = "165--171",

editor = "Valerie King and Le, {Hung Viet}",

booktitle = "4th Symposium on Simplicity in Algorithms, SOSA 2021",

address = "United States",

}