Sublinear estimation of weighted matchings in dynamic data streams

DOI10.1007/978-3-662-48350-3_23MaRDI QIDQ3452791zbMATH OpenOpenAlexFDO

Authors Marc Bury, Chris Schwiegelshohn

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.02019

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Analysis of algorithms (68W40) Approximation algorithms (68W25)

Abstract: This paper presents an algorithm for estimating the weight of a maximum weighted matching by augmenting any estimation routine for the size of an unweighted matching. The algorithm is implementable in any streaming model including dynamic graph streams. We also give the first constant estimation for the maximum matching size in a dynamic graph stream for planar graphs (or any graph with bounded arboricity) using $ildeO(n^{4/5})$ space which also extends to weighted matching. Using previous results by Kapralov, Khanna, and Sudan (2014) we obtain a $mathrmpolylog(n)$ approximation for general graphs using $mathrmpolylog(n)$ space in random order streams, respectively. In addition, we give a space lower bound of $Omega(n^{1-varepsilon})$ for any randomized algorithm estimating the size of a maximum matching up to a $1+O(varepsilon)$ factor for adversarial streams.

Recommendations

• Structural results on matching estimation with applications to streaming
• Planar matching in streams revisited
• On estimating maximum matching size in graph streams
• The sparse awakens: streaming algorithms for matching size estimation in sparse graphs
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques

Cites work

• scientific article; zbMATH DE number 3698383 (Why is no real title available?)
• scientific article; zbMATH DE number 1424324 (Why is no real title available?)
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Dynamic Graphs in the Sliding-Window Model
• Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography
• Exponential Separation of Quantum and Classical One-Way Communication Complexity
• Graph Sparsification in the Semi-streaming Model
• Improved approximation guarantees for weighted matching in the semi-streaming model
• Improved bounds for online preemptive matching
• Improved streaming algorithms for weighted matching, via unweighted matching
• Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams
• Maximum matching in semi-streaming with few passes
• Maximum matching in turnstile streams
• Numerical linear algebra in the streaming model
• On graph problems in a semi-streaming model
• Parallel approximation algorithms for maximum weighted matching in general graphs
• Pseudorandom generators for space-bounded computation
• Spectral sparsification in dynamic graph streams
• Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond
• The Factorization of Linear Graphs
• The streaming complexity of cycle counting, sorting by reversals, and other problems
• Turnstile streaming algorithms might as well be linear sketches
• Weighted matching in the semi-streaming model

Cited in

(16)

• Dynamic graph stream algorithms in \(o(n)\) space
• Structural results on matching estimation with applications to streaming
• Graph sketching and streaming: new approaches for analyzing massive graphs
• Planar matching in streams revisited
• A simple, space-efficient, streaming algorithm for matchings in low arboricity graphs
• The sparse awakens: streaming algorithms for matching size estimation in sparse graphs
• Sublinear-space streaming algorithms for estimating graph parameters on sparse graphs
• On approximating matrix norms in data streams
• Improved bounds for matching in random-order streams
• On estimating maximum matching size in graph streams
• (Noisy) gap cycle counting strikes back: random order streaming lower bounds for connected components and beyond
• Streaming Euclidean MST to a constant factor
• Deterministic algorithms for maximum matching on general graphs in the semi-streaming model
• Weighted matching in the random-order streaming and robust communication models
• Almost-smooth histograms and sliding-window graph algorithms
• Maximum matching in two, three, and a few more passes over graph streams

This page was built for publication: Sublinear estimation of weighted matchings in dynamic data streams

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