2020/02/18 by Davin Choo, Choo, Davin, Christoph Grunau +5 · 5 citations
Computer Science · Mathematics · #Algorithm #Applied mathematics #Approximation algorithm #Binary logarithm #Cluster analysis #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Constant (computer programming) #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and Algorithms #Mathematics #Physics #State (computer science) #Statistics #Yield (engineering) #cs.DS #cs.LG #k-means clustering
paper · pdf · doi:10.48550/arxiv.2002.07784
published in arXiv (Cornell University) (Cornell University)
arxiv created 2020/02/18 · openalex publication_date 2020/02/18 · arxiv updated 2020/02/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The k-means++ algorithm of Arthur and Vassilvitskii (SODA 2007) is a state-of-the-art algorithm for solving the k-means clustering problem and is known to give an O(log k)-approximation in expectation. Recently, Lattanzi and Sohler (ICML 2019) proposed augmenting k-means++ with O(k log log k) local search steps to yield a constant approximation (in expectation) to the k-means clustering problem. In this paper, we improve their analysis to show that, for any arbitrarily small constant \eps > 0, with only \eps k additional local search steps, one can achieve a constant approximation guarantee (with high probability in k), resolving an open problem in their paper.