Space Lower Bounds for Approximating Maximum Matching in the Edge Arrival Model
Michael Kapralov
Abstract
The bipartite matching problem in the online and streaming settings has received a lot of attention recently. The classical vertex arrival setting, for which the celebrated Karp, Vazirani and Vazirani (KVV) algorithm achieves a 1 – 1/e approximation, is rather well understood: the 1 – 1/e approximation is optimal in both the online and semi-streaming setting, where the algorithm is constrained to use n · logO(1) n space. The more challenging the edge arrival model has seen significant progress recently in the online algorithms literature. For the strictly online model (no preemption) approximations better than trivial factor 1/2 have been ruled out [Gamlath et al'FOCS'19]. For the less restrictive online preemptive model a better than -approximation [Epstein et al'STACS'12] and even a better than -approximation[Huang et al'SODA'19] have been ruled out. The recent hardness results for online preemptive matching in the edge arrival model are based on the idea of stringing together multiple copies of a KVV hard instance using edge arrivals. In this paper, we show how to implement such constructions using ideas developed in the literature on Ruzsa-Szemerédi graphs. As a result, we show that any single pass streaming algorithm that approximates the maximum matching in a bipartite graph with n vertices to a factor better than requires n1+Ω(1/ log log n) » n logO(1) n space. This gives the first separation between the classical one sided vertex arrival setting and the edge arrival setting in the semi-streaming model.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
17 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time cites Deterministic (1+ε)-approximate maximum matching with poly(1/ε) passes in the semi-streaming model and beyond
- Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time cites Dynamic Algorithms for Maximum Matching Size
- Dynamic Algorithms for Maximum Matching Size cites Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time
- On Regularity Lemma and Barriers in Streaming and Dynamic Matching cites Deterministic (1+ε)-approximate maximum matching with poly(1/ε) passes in the semi-streaming model and beyond
- Deterministic (1+ε)-approximate maximum matching with poly(1/ε) passes in the semi-streaming model and beyond cites Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples
- Dynamic Algorithms for Maximum Matching Size cites On Regularity Lemma and Barriers in Streaming and Dynamic Matching
Cited by top-tier papers17
- Fairness in Streaming Submodular Maximization over a Matroid ConstraintMarwa El Halabi, Federico Fusco, Ashkan Norouzi-Fard, Jakab Tardos et al.ICML 2023 · 15 citations
- Dynamic Algorithms for Maximum Matching SizeSoheil BehnezhadSODA 2023 · 14 citations
- On Regularity Lemma and Barriers in Streaming and Dynamic MatchingSepehr Assadi, Soheil Behnezhad, Sanjeev Khanna, Huan LiSTOC 2023 · 13 citations
- Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update TimeSayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak, David WajcSODA 2023 · 11 citations
- Deterministic (1+ε)-approximate maximum matching with poly(1/ε) passes in the semi-streaming model and beyondManuela Fischer, Slobodan Mitrovic, Jara UittoSTOC 2022 · 11 citations
Builds on1
Related papers
- Hidden Permutations to the Rescue: Multi-Pass Streaming Lower Bounds for Approximate MatchingsSepehr Assadi, Janani SundaresanFOCS 2023 · 3 citations
- Approximate Maximum Matching in Random StreamsAlireza Farhadi, Mohammad Taghi Hajiaghayi, Tung Mai, Anup Rao et al.SODA 2020 · 14 citations
- Semi-streaming Matching in a Single Pass: A New Framework for Lower Bounds via BlueprintsSepehr Assadi, Max Jiang, Mars XiangSTOC 2026 · 4 citations
- An Unconditional Lower Bound for Two-Pass Streaming Algorithms for Maximum Matching ApproximationChristian Konrad, Kheeran K. NaiduSODA 2024 · 1 citation
- A Two-Pass (Conditional) Lower Bound for Semi-Streaming Maximum MatchingSepehr AssadiSODA 2022 · 7 citations
