Recent Advances in Diversity Maximization in the Offline and Composable Coreset Models
summary
Survey presents concrete algorithms and bounds: a composable coreset construction achieves composable coreset of size k^{1+ε} with 1/ε approximation for the sum-of-nearest-neighbor objective, built by greedy clustering, a k^2 baseline, improvement to k^{1.5} and then k^{1+ε} via an S/T pair-finding using the r̂ radius. Matching-based diversity improves from log k to constant approximation. Experiments show 100× speedup with few-percent quality loss and report empirical losses under partition constraints: sum-pairwise 1%, nearest-neighbor 20%, min-pairwise 50%.
AI-written summary · about
chapters (7)
- 0:00Diversity maximization intro
- 7:57Composable coresets background
- 13:40Coreset results for diversity
- 27:39Two sets with max distance
- 34:56Constrained diversity generalization
- 39:34Experimental results
- 40:59Q&A
related talks
52mConstrained Subset Selection Problems under Diversity Measures
29mSampling Algorithms for Combinatorial Pure Exploration
33mComputation-Statistics Tradeoffs in Unsupervised Learning via Data Summarization
33mOnline Multiserver Convex Chasing and Optimization
01h 00mStreaming Euclidean k-median and k-means with o(log n) Space
47mSuccinct Representations and Efficient Algorithms Based on Linear Programming
01h 08mData Driven Optimization Models and Algorithms
01h 04mSubmodularity: Theory and Applications II