A Constant-Factor Bi-Criteria Approximation Guarantee for k-means++
| 
49 | 
39 | 
0
Abstract
This paper studies the k-means++ algorithm for clustering as well as the class of 
sampling algorithms to which k-means++ belongs. It is shown that for any constant factor 
> 1, selecting k cluster centers by sampling yields a constant-factor approximation to the optimal clustering with k centers, in expectation and without conditions on the dataset. This result extends the previously known O(log k) guarantee for the case = 1 to the constant-factor bi-criteria regime. It also improves upon an existing constant-factor bi-criteria result that holds only with constant probability.
还没有评论，说两句吧！
热门资源
The Variational S...
Unlike traditional images which do not offer in...
Learning to Predi...
Much of model-based reinforcement learning invo...
Stratified Strate...
In this paper we introduce Stratified Strategy ...
A Mathematical Mo...
Direct democracy, where each voter casts one vo...
Rating-Boosted La...
The performance of a recommendation system reli...
智能在线
400-630-6780
聆听.建议反馈
E-mail: support@tusaishared.com
资源分类
