Space Lower Bounds for Approximating Maximum Matching in the Edge Arrival Model
share
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·log^O(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 1/1+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é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 1/1+ln 2≈ 0.59 requires n^1+Ω(1/loglog n)≫ n log^O(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.
READ FULL TEXT