In this paper we present improved bounds for approximating maximum matchings in bipartite graphs in the streaming model. First, we consider the question of how well maximum matching can be approximated in a single pass over the input whenÕ(n) space is allowed, where n is the number of vertices in the input graph. Two natural variants of this problem have been considered in the literature: (1) the edge arrival setting, where edges arrive in the stream and (2) the vertex arrival setting, where vertices on one side of the graph arrive in the stream together with all their incident edges. The latter setting has also been studied extensively in the context of online algorithms, where each arriving vertex has to either be matched irrevocably or discarded upon arrival. In the online setting, the celebrated algorithm of KarpVazirani-Vazirani achieves a 1 − 1/e approximation by crucially using randomization (and usingÕ(n) space). Despite the fact that the streaming model is less restrictive in that the algorithm is not constrained to match vertices irrevocably upon arrival, the best known approximation in the streaming model with vertex arrivals andÕ(n) space is the same factor of 1 − 1/e. We show that no (possibly randomized) single pass streaming algorithm constrained to useÕ(n) space can achieve a better than 1 − 1/e approximation to maximum matching, even in the vertex arrival setting. This leads to the striking conclusion that no single pass streaming algorithm can get any advantage over online algorithms unless it uses significantly more thanÕ(n) space. Additionally, our bound yields the best known impossibility result for approximating matchings in the edge arrival model (improving upon the bound of 2/3 proved by Goel at al [SODA'12]). Second, we consider the problem of approximating matchings in multiple passes in the vertex arrival setting. We show that a simple fractional load balancing approach achieves approximation ratio + o(1/k) in k passes using linear space. Thus, our algorithm achieves the best possible 1 − 1/e approximation in a single pass and improves upon the 1 − O( log log k/k) approximation in k passes due to Ahn and Guha [ICALP'11]. Additionally, our approach yields an efficient solution to the Gap-Existence problem considered by Charles et al [EC'10].
As for hardness results, REF showed that no algorithm can achieve a better approximation guarantee than (1 − 1 /e) in the adversarial single pass streaming setting.
Better bounds for matchings in the streaming model
arXiv: Data Structures and Algorithms
Computer Science Mathematics