Online Clustering with Nearly Optimal Consistency
T-H. Hubert Chan Shaofeng H.-C. Jiang Tianyi Wu Mengshi Zhao
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 $\alpha$-approximate offline algorithm for clustering into an $(1+\epsilon)\alpha^2$-competitive online algorithm for clustering with $O(k \text{poly} \log n)$ consistency. 
This consistency bound is optimal up to $\text{poly} \log(n)$ factors. 
Plugging in the offline algorithm that returns the exact optimal solution, 
we obtain the first
$(1 + \epsilon)$-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.
clustering, online, consistency
(1 + eps)-competitive online clustering algorithms with O(k polylog n) consistency