论文标题
改进的K-Means ++和K-Means ++平行的保证
Improved Guarantees for k-means++ and k-means++ Parallel
论文作者
论文摘要
在本文中，我们研究K-均值++和K-均值++平行的，这是经典K-均值聚类问题的两种最受欢迎的算法。我们提供新的分析，并显示了K-Means ++和K-Means ++平行的近似值和双标准近似保证。我们的结果为这些算法在实践中表现出色的原因提供了更好的理论理由。我们还提出了一种新的K-Means ++并行算法（指数race k-Means ++）的变体，该算法具有与K-均值++相同的近似保证。
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++.
