Succinct Representations and Efficient Algorithms Based on Linear Programming
Talkat Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013) · 2013-09-16..09-19·
summary
Shows how to compute a 1 - ε approximation to maximum cardinality matching in non‑bipartite graphs in a semi‑streaming/map‑reduce style model using p/ε passes and roughly n^{1+1/p} space, with running time dominated by sketching inner products. Key tools are total dual integrality to bound LP width, a primal–dual reduction that asks an oracle for dense odd sets, and a deferred specification trick plus cut sparsifiers/sketches to collapse adaptivity so the algorithm accesses the raw edges only in few passes.
AI-written summary · about
chapters (24)
- 0:00Intro
- 3:05Representation = Optimization
- 4:06Resource Constrained Computations
- 5:14Semi-Streaming
- 7:27That being said...
- 9:20Specific Example Problem
- 10:32The Standard LP
- 13:08The overall plan
- 13:37Approximately Solving LPs
- 14:52The Canonical Setup
- 16:38Multiplicative Weights Update
- 20:10Fractional Covering and Packing
- 23:25Paying the piper?
- 24:31A Dual-Primal Framework
- 25:50An Elenchus
- 27:46A Dual-Primal on Matching
- 29:22The task for the Oracle
- 30:42A Maximal Covering
- 33:22The Width
- 34:10What is the algorithm doing?
- 37:07One comes back!!
- 38:17A One-Two Punch: One, finally
- 39:21The One-Two Punch: Two
- 41:36So what happened?
related talks
29mSampling Algorithms for Combinatorial Pure Exploration
42mLearning What Works Best When
01h 00mOn Approximating the Covering Radius and Finding Dense Lattice Subspaces
51mMin-max Optimization: From Complexity to Algorithms
01h 26mStreaming, Sketching and Sufficient Statistics II
52mMax Cut with Linear Programs: Sherali-Adams Strikes Back
46mRecent Advances in Diversity Maximization in the Offline and Composable Coreset Models
33mLearning the Best Agorithm for Max-Cut, Clustering, and Other Partitioning Problems