Online Clustering with Nearly Optimal Consistency

We give online algorithms for k-MEANS (more generally, (k, z)-CLUSTERING) with nearly optimal consistency (a notion suggested by Lattanzi & Vassilvitskii (2017)). Our result turns any α-approximate offline algorithm for clustering into a (1 + ϵ)α 2 -competitive online algorithm for clustering with O(k poly log n) consistency. This consistency bound is optimal up to poly log(n) factors. Plugging in the offline algorithm that returns the exact optimal solution, we obtain the first (1 + ϵ)-competitive online algorithm for clustering that achieves a linear in k consistency. This simultaneously improves several previous results (Lattanzi & Vassilvitskii, 2017;Fichtenberger et al., 2021). We validate the performance of our algorithm on real datasets by plugging in the practically efficient k-MEANS++ algorithm. Our online algorithm makes k-MEANS++ achieve good consistency with little overhead to the quality of solutions.