Dynamic Matching: Rounding & Sparsification (And New Tools)
summary
Shows how to convert dynamic fractional matchings into integral matchings using sparsification via rounding and bulk sampling by edge‑coloring, reducing prior ε^-4 dependence toward an essentially 1/ε barrier; constructs adaptive, polylog‑update routines and deterministic variants that produce 1/2−ε (and near 1−ε in bipartite) guarantees; introduces fast almost maximal matching and optimal dynamic subset sampling primitives that are robust to adaptive adversaries and run in polylog (or constant) amortized time.
AI-written summary · about
chapters (20)
- 0:00Introduction
- 2:25Dynamic Matching
- 3:09Background
- 4:10Goals
- 5:19Rounding
- 7:06Interface
- 8:24Roadmap
- 8:50Sparsification
- 12:09Sparsifier
- 17:03Integral Results
- 18:49Adaptive Rounding
- 20:26Periodic Sparsification
- 22:47Sampling via Edge Coloring
- 31:17deterministic approach
- 34:51state of the art
- 38:26partial rounding
- 40:40new tools
- 42:47summary
- 43:45techniques tools
- 44:35interactive questions