论文标题
K-均值++：几乎没有步骤产生常数近似
k-means++: few more steps yield constant approximation
论文作者
论文摘要
Arthur和Vassilvitskii的K-Means ++算法（Soda 2007）是一种用于解决K-均值聚类问题的最先进算法，并且众所周知可以在预期中给出O（log k）Appproximation。最近，Lattanzi和Sohler（ICML 2019）提出了使用O（k log log K）本地搜索步骤增强K-Means ++，以产生恒定的近似值（预期），以使K-Means集群问题出现。在本文中，我们改进了他们的分析，以表明，对于任何任意小的常数$ \ eps> 0 $，只有$ \ eps k $附加的本地搜索步骤，就可以实现恒定的近似保证（k中的概率很高），从而在他们的论文中解决了一个开放的问题。
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.
