Quotient Sparsification for Submodular Functions
summary
Proves a single theorem that sparsifies any monotone submodular function by sampling a weighted subset of elements of size O(r log n / ε^2) and preserves the weight of every quotient up to 1+ε with high probability; yields n log n / ε^2 hyperedges for hypergraph k‑cut preservation, D log n / ε^2 vectors for linear quotients, and element counts proportional to number of sets for coverage. Algorithms run randomized polynomial or nearly linear time using Benczúr–Karger style decompositions, Karger contractions and Frank–Miklós push–relabel ideas.
AI-written summary · about
chapters (10)
- 0:00Introduction to graph cuts
- 1:34Cut sparsification overview
- 3:13Generalizing to hypergraphs
- 5:36Matroids and definitions
- 8:26Rank and quotient concepts
- 12:15Matroid quotient results
- 14:25Submodular function applications
- 17:53Linear spaces and coverage
- 20:29Precedents and methodology
- 24:29Concluding thoughts and Q&A