Semi-Streaming Bipartite Matching in Fewer Passes and Optimal Space

Sepehr Assadi, Arun Jambulapati, Yujia Jin, Aaron Sidford, Kevin Tian

Research output: Chapter in Book/Report/Conference proceedingConference contribution

15 Scopus citations

Abstract

We provide eO(1)-pass semi-streaming algorithms for computing (1)-approximate maximum cardinality matchings in bipartite graphs. Our most eficient methods are deterministic and use optimal, O(n), space, improving upon the space complexity of the previous state-of-the-art eO(1)-pass algorithm of [AG18]. To obtain our results we provide semi-streaming adaptations of more general continuous optimization tools. Further, we leverage these techniques to obtain improvements for streaming variants of approximate linear programming, optimal transport, exact matching, transshipment, and shortest path problems.

Original languageEnglish (US)
Title of host publicationACM-SIAM Symposium on Discrete Algorithms, SODA 2022
PublisherAssociation for Computing Machinery
Pages627-669
Number of pages43
ISBN (Electronic)9781611977073
StatePublished - 2022
Event33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022 - Alexander, United States
Duration: Jan 9 2022Jan 12 2022

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume2022-January

Conference

Conference33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022
Country/TerritoryUnited States
CityAlexander
Period1/9/221/12/22

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics

Fingerprint

Dive into the research topics of 'Semi-Streaming Bipartite Matching in Fewer Passes and Optimal Space'. Together they form a unique fingerprint.

Cite this