Coresets and Their Applications to Design Sublinear Algorithms
summary
Coresets are small weighted subsets that provably approximate optimization costs: 1-center reduces to 2 points with a constant factor, k‑center uses Gonzalez greedy to get k+1 points, and directional-width coresets use an epsilon‑net of size about 1/ε^{d−1}. Sensitivity sampling yields k‑median coresets of size ≈ k^2 d / ε^2. Composable coresets (unionable summaries) enable streaming via √n chunks; local search gives a size‑k composable coreset for volume with roughly k^k approximation, and random partitions can improve impossible worst‑case bounds.
AI-written summary · about
chapters (8)
- 0:00Introduction to corsets
- 1:01Defining the corset concept
- 7:38Constructing directional widths
- 10:25Clustering and corsets
- 20:32Sensitivity sampling
- 26:06Composable corsets
- 30:52Diversity maximization
- 47:46Conclusion and Q&A
related talks
41mScalable Spatial Scan Statistics with Coresets
35mSampling for Subset Selection and Applications
25mUsing Set Cover to Optimize a Large-Scale Low Latency Distributed Graph
01h 09mSketching High-Dimensional Data
48mRandomized Numerical Linear Algebra
01h 26mStreaming, Sketching and Sufficient Statistics II
36mDistributed Partial Clustering
01h 13mSketching High-Dimensional Data