Maximum Matching in Turnstile Streams

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

34 Citations (Scopus)
212 Downloads (Pure)

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 languageEnglish
Title of host publicationAlgorithms - ESA 2015
Subtitle of host publication23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings
PublisherSpringer Berlin Heidelberg
Pages840-852
Number of pages13
Volume9294
ISBN (Electronic)9783662483503
ISBN (Print)9783662483497
DOIs
Publication statusPublished - 12 Nov 2015

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume9294
ISSN (Print)0302-9743

Keywords

  • Input Graph
  • Maximum Match
  • Vertex Group
  • Bipartite Match
  • Edge Insertion

Fingerprint Dive into the research topics of 'Maximum Matching in Turnstile Streams'. Together they form a unique fingerprint.

Cite this