Abstract
We consider the unweighted bipartite maximum matching problem in the one-pass turnstile streaming model where the input stream consists of edge insertions and deletions. In the insertion-only model, a one-pass 2-approximation streaming algorithm can be easily obtained with space O(n logn), where n denotes the number of vertices of the input graph. We show that no such result is possible if edge deletions are allowed, even if space O(n3/2 − δ) is granted, for every δ > 0. Specifically, for every 0 ≤ ε ≤ 1, we show that in the one-pass turnstile streaming model, in order to compute a O(n ε )-approximation, space Ω(n3/2 − 4ε) is required for constant error randomized algorithms, and, up to logarithmic factors, space O~(n2−2ϵ) is sufficient.
Our lower bound result is proved in the simultaneous message model of communication and may be of independent interest.
Original language | English |
---|---|
Title of host publication | Algorithms - ESA 2015 |
Subtitle of host publication | 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings |
Publisher | Springer Berlin Heidelberg |
Pages | 840-852 |
Number of pages | 13 |
Volume | 9294 |
ISBN (Electronic) | 9783662483503 |
ISBN (Print) | 9783662483497 |
DOIs | |
Publication status | Published - 12 Nov 2015 |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Publisher | Springer |
Volume | 9294 |
ISSN (Print) | 0302-9743 |
Keywords
- Input Graph
- Maximum Match
- Vertex Group
- Bipartite Match
- Edge Insertion