On Two-Pass Streaming Algorithms for Maximum Bipartite Matching

Christian Konrad, Kheeran K. Naidu

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

13 Citations (Scopus)

Abstract

We study two-pass streaming algorithms for Maximum Bipartite Matching (MBM). All known two-pass streaming algorithms for MBM operate in a similar fashion: They compute a maximal matching in the first pass and find 3-augmenting paths in the second in order to augment the matching found in the first pass. Our aim is to explore the limitations of this approach and to determine whether current techniques can be used to further improve the state-of-the-art algorithms. We give the following results:
We show that every two-pass streaming algorithm that solely computes a maximal matching in the first pass and outputs a (2/3+ε)-approximation requires n^{1+Ω(1/(log log n))} space, for every ε > 0, where n is the number of vertices of the input graph. This result is obtained by extending the Ruzsa-Szemerédi graph construction of [Goel et al., SODA'12] so as to ensure that the resulting graph has a close to perfect matching, the key property needed in our construction. This result may be of independent interest.
Furthermore, we combine the two main techniques, i.e., subsampling followed by the Greedy matching algorithm [Konrad, MFCS'18] which gives a 2-√2 ≈ 0.5857-approximation, and the computation of degree-bounded semi-matchings [Esfandiari et al., ICDMW'16][Kale and Tirodkar, APPROX'17] which gives a 1/2 + 1/12 ≈ 0.5833-approximation, and obtain a meta-algorithm that yields Konrad’s and Esfandiari et al.’s algorithms as special cases. This unifies two strands of research. By optimizing parameters, we discover that Konrad’s algorithm is optimal for the implied class of algorithms and, perhaps surprisingly, that there is a second optimal algorithm. We show that the analysis of our meta-algorithm is best possible. Our results imply that further improvements, if possible, require new techniques.
Original languageEnglish
Title of host publicationApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Subtitle of host publication16th International Workshop, APPROX 2013, and 17th International Workshop, RANDOM 2013, Berkeley, CA, USA, August 21-23, 2013, Proceedings
EditorsMary Wootters, Laura Sanità
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages19:1-19:18
Volume207
DOIs
Publication statusPublished - 15 Sept 2021
EventAPPROX/RANDOM 2021 - Online
Duration: 16 Aug 202118 Aug 2021
https://randomconference.com/random-2021-home/

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
ISSN (Print)1868-8969

Conference

ConferenceAPPROX/RANDOM 2021
Period16/08/2118/08/21
Internet address

Fingerprint

Dive into the research topics of 'On Two-Pass Streaming Algorithms for Maximum Bipartite Matching'. Together they form a unique fingerprint.

Cite this