Online Multiserver Convex Chasing and Optimization
summary
Shows a constructive reduction that turns online k-means into a k-server style procedure and yields an order k^2 competitive algorithm (uses an order-k k-server subroutine and incurs an extra k factor at one step). Proves 1D admits a simple double-coverage style 4k guarantee, proves chasing arbitrary convex sets in 2D is impossible but k-means is solvable by switching to blind move-to-minimum and rescaling squared to linear distances with per-request factors.
AI-written summary · about
chapters (9)
- 0:00Intro
- 1:03k-means clustering
- 3:10Online clustering
- 11:04k-server + chasing
- 14:12k-chasing convex functions on the line
- 19:44Online k-means
- 22:08Illustration
- 23:18A sequence of reductions
- 27:25More results
related talks
46mRecent Advances in Diversity Maximization in the Offline and Composable Coreset Models
01h 04mCompetitive Analysis of Online Algorithms (Part 2)
01h 00mStreaming Euclidean k-median and k-means with o(log n) Space
26mMathematical Approaches to Clustering
28mCertified Sub-Linear Lower Bounds for K-Means Clustering
48mOnline Adversarial Multicalibration And (Multi)Calibeating
42mk-means and k-medians under Dimension Reduction
27mDouble Coverage with Machine-Learned Advice