K-means++ is an important algorithm to choose initial cluster centers for the k-means clustering algorithm. In this work, we present a new algorithm that can solve the $k$-means++ problem with near optimal running time. Given $n$ data points in $\mathbb{R}^d$, the current state-of-the-art algorithm runs in $\widetilde{O}(k )$ iterations, and each iteration takes $\widetilde{O}(nd k)$ time. The overall running time is thus $\widetilde{O}(n d k^2)$. We propose a new algorithm \textsc{FastKmeans++} that only takes in $\widetilde{O}(nd + nk^2)$ time, in total.

翻译：K- means++ 是选择 k- means 群集算法初始集集中心的重要算法 。 在这项工作中, 我们提出一种新的算法, 可以在接近最佳运行时间的情况下解决 $k$- means++ 的问题。 考虑到$\ mathb{R ⁇ d$ 的数据点, 当前最先进的算法以$\ loblytilde{O} (k) $( lax) 来运行, 且每次循环需要$\ 全局tilde{ O} (n k) 时间 。 因此, 整个运行时间是$\ loblytelde{ (n d k) 2 。 我们建议使用新的算法 \ textsc{ FastKmeles *, 总共只需要 $\\ loblytilde{ O} (nd + nk} 2 时间 。