# Space Lower Bounds for Approximating Maximum Matching in the Edge Arrival Model

arXiv: https://arxiv.org/abs/2103.11669 · HTML: https://mlsanity.com/paper/2103.11669/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Mar 2021.

## Built on by (most cited first, 2 of 2)

- [Fairness in Streaming Submodular Maximization over a Matroid Constraint](https://mlsanity.com/paper/2305.15118/) (2023)
- [Stochastic Matching via Local Sparsification](https://mlsanity.com/paper/2605.14195/) (2026)

## Abstract (arXiv)

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 frac11+ln 2-approximation [Epstein et al'STACS'12] and even a better than (2-√2)-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'edi 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 frac11+ln 2≈ 0.59 requires n1+Omega(1/loglog n)gg 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.