Maximum matching in turnstile streams

DOI10.1007/978-3-662-48350-3_70MaRDI QIDQ3452845zbMATH OpenOpenAlexFDO

Authors Christian Konrad

Publication date 19 November 2015

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

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

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)

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.

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

Cites work

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

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
• Structural results on matching estimation with applications to streaming
• Independent sets in vertex-arrival streams
• 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)