Distributed Partial Clustering
Talkat Optimization and Decision-Making Under Uncertainty (Simons Institute, September 2016) · 2016-09-19..09-23·
summary
Distributed clustering with T outliers and an arbitrary partition across s sites achieves a one‑round constant‑factor approximation by having each site compute local solutions for powers‑of‑two outlier budgets and send compact summaries: log T marginals and local centers. A coordinator convexifies these profiles and uses water‑filling convex lower envelope to assign outlier quotas summing to T, then clusters the reduced instance. The method (a clustering of clusterings meta‑algorithm) applies to k‑median, k‑means and k‑center, cuts communication well below s·k+T, and speeds n^2 time to roughly n^2/s.
AI-written summary · about
chapters (11)
- 0:00Start
- 0:32What Is Partial Optimization
- 2:22Why Should We Care about Partial Optimization
- 4:19Adaptive Refinement
- 5:44Distributed Partial Optimization
- 7:22Oracle Distance Model
- 14:19Why Does this Work
- 14:35Provably Good Clustering
- 15:30Moving or Perturbing the Points
- 24:19Sub Clustering Problem What Is the Sub Clustering Problem
- 28:07Probabilistic Clustering
related talks
35mSampling for Subset Selection and Applications
37mApproaches to online quantile estimation
01h 04mSampling Big Ideas in Sublinear Algorithms
52mCoresets and Their Applications to Design Sublinear Algorithms
48mRandomized Numerical Linear Algebra
01h 09mSketching High-Dimensional Data
41mIntegrating Functions via Distance Sensitive Hashing
32mBigData Clustering Illustrated by OK Gifts