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

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.