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.
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 language | English |
---|---|
Title of host publication | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques |
Subtitle of host publication | 16th International Workshop, APPROX 2013, and 17th International Workshop, RANDOM 2013, Berkeley, CA, USA, August 21-23, 2013, Proceedings |
Editors | Mary Wootters, Laura Sanità |
Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
Pages | 19:1-19:18 |
Volume | 207 |
DOIs | |
Publication status | Published - 15 Sept 2021 |
Event | APPROX/RANDOM 2021 - Online Duration: 16 Aug 2021 → 18 Aug 2021 https://randomconference.com/random-2021-home/ |
Publication series
Name | Leibniz International Proceedings in Informatics (LIPIcs) |
---|---|
Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
ISSN (Print) | 1868-8969 |
Conference
Conference | APPROX/RANDOM 2021 |
---|---|
Period | 16/08/21 → 18/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.Student theses
-
Streaming Maximum Matching in a Few Passes: Algorithms and Lower Bounds
Naidu, K. K. (Author), Clifford, R. (Supervisor) & Konrad, C. (Supervisor), 1 Oct 2024Student thesis: Doctoral Thesis › Doctor of Philosophy (PhD)
File