Maximum matching in turnstile streams

DOI10.1007/978-3-662-48350-3_70zbMATH Open1466.68088arXiv1505.01460OpenAlexW2225286048MaRDI QIDQ3452845FDOQ3452845

Authors: Christian Konrad 

Publication date: 19 November 2015

Published in: Algorithms - ESA 2015 (Search for Journal in Brave)

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(nlogn)$, 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(n^{3/2-delta})$ is granted, for every $delta>0$. Specifically, for every $0leepsilonle1$, we show that in the one-pass turnstile streaming model, in order to compute a $O(n^{epsilon})$-approximation, space $Omega(n^{3/2-4epsilon})$ is required for constant error randomized algorithms, and, up to logarithmic factors, space $O(n^{2-2epsilon})$ is sufficient. Our lower bound result is proved in the simultaneous message model of communication and may be of independent interest.

Full work available at URL: https://arxiv.org/abs/1505.01460

Recommendations

• Better bounds for matchings in the streaming model
• Approximating matching size from random streams
• Maximum matchings in dynamic graph streams and the simultaneous communication model
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• scientific article; zbMATH DE number 7053293

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Randomized algorithms (68W20) Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Dynamic Graphs in the Sliding-Window Model
• Data streams: algorithms and applications.
• On graph problems in a semi-streaming model
• Weighted matching in the semi-streaming model
• Bipartite matching in the semi-streaming model
• Linear programming in the semi-streaming model with application to the maximum matching problem
• Maximum matching in semi-streaming with few passes
• Superlinear lower bounds for multipass graph processing
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Spectral sparsification in dynamic graph streams
• Single pass spectral sparsification in dynamic streams
• Improved streaming algorithms for weighted matching, via unweighted matching
• Spanners and sparsifiers in dynamic streams
• Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond
• IMPROVED APPROXIMATION GUARANTEES FOR WEIGHTED MATCHING IN THE SEMI-STREAMING MODEL *
• Turnstile streaming algorithms might as well be linear sketches

Cited In (19)

• Optimal lower bounds for matching and vertex cover in dynamic graph streams
• Querying a Matrix Through Matrix-Vector Products.
• Optimality of linear sketching under modular updates
• Communication complexity of approximate maximum matching in the message-passing model
• Sublinear estimation of weighted matchings in dynamic data streams
• Maximum matchings in dynamic graph streams and the simultaneous communication model
• Approximate Maximum Matching in Random Streams
• Dynamic graph stream algorithms in \(o(n)\) space
• Independent sets in vertex-arrival streams
• Structural results on matching estimation with applications to streaming
• Better streaming algorithms for the maximum coverage problem
• A simple augmentation method for matchings with applications to streaming algorithms
• Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams.
• Improved bounds for matching in random-order streams
• Better bounds for matchings in the streaming model
• On regularity lemma and barriers in streaming and dynamic matching
• High probability frequency moment sketches
• Deterministic algorithms for maximum matching on general graphs in the semi-streaming model
• Maximum matching in two, three, and a few more passes over graph streams

This page was built for publication: Maximum matching in turnstile streams

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3452845)