Streaming Algorithms for Matchings in Low Arboricity Graphs
summary
Provides an alpha+2 approximation to maximum matching size in graphs of arboricity alpha via three streaming algorithms: a dynamic-stream method using sampling and degree sketches that runs in about n^{4/5} space and handles deletions by splitting small/large-match cases, an insert-only variant that keeps the same approximation with logarithmic space by adaptive sampling of alpha-bounded edges, and an adjacency-list algorithm that computes the quantity exactly in constant space using degree counters and fractional-matching bounds.
AI-written summary · about
chapters (12)
- 0:00Introduction
- 0:24Streaming Model
- 1:35Streaming Models
- 2:39Objectives
- 4:44Edge Sampling
- 6:12Maximum Matching
- 7:53Optimal Matching
- 12:34Structural Results
- 13:05Sigma Dynamic
- 16:00Sigma Insert
- 20:03Dynamic Streams
- 24:38Insert only streams
related talks
01h 21mAn Overview on Data Streams Algorithms
01h 04mNew Algorithms for Heavy Hitters in Data Streams
01h 26mStreaming, Sketching and Sufficient Statistics II
01h 24mStreaming, Sketching and Sufficient Statistics I
01h 04mSampling Big Ideas in Sublinear Algorithms
48mHomomorphic Sketches: Shrinking Big Data without Sacrificing Structure
01h 09mSketching High-Dimensional Data
19mGraphs as Streams: Rethinking Graph Processing in ... #bbuzz