Improved Guarantees for k-means++ and k-means++ Parallel
Improved Guarantees for k-means++ and k-means++ Parallel
复制标题
DOI：
--
复制
发表时间：
2020-10
期刊：
影响因子：
--
通讯作者：
K. Makarychev;Aravind Reddy;Liren Shan
中科院分区：
文献类型：
--
作者：
K. Makarychev;Aravind Reddy;Liren Shan
在本文中，我们研究了k-means++和k-means++ parallel这两种最流行的算法来解决经典的k-means++聚类问题。我们提供了新的分析，并展示了k-means++和k-means++并行的改进近似和双准则近似保证。我们的结果为为什么这些算法在实践中表现得非常好提供了更好的理论依据。我们还提出了k-means++并行算法的一个新变体（指数竞赛k-means++），它具有与k-means++相同的近似保证。
In this paper, we study k-means++ and k-means++ parallel, the two most popular algorithms for the classic k-means clustering problem. We provide novel analyses and show improved approximation and bi-criteria approximation guarantees for k-means++ and k-means++ parallel. Our results give a better theoretical justification for why these algorithms perform extremely well in practice. We also propose a new variant of k-means++ parallel algorithm (Exponential Race k-means++) that has the same approximation guarantees as k-means++.