# Transactions on Machine Learning and Data Mining (ISSN: 1865-6781)

## Volume 3 - Number 2 - October 2010 - Pages 67-79

### Fast Algorithms for Constant Approximation k-Means Clustering

M. Song and S. Rajasekaran

Computer Science and Engineering, University of Connecticut

Storrs CT 06269, USA

** Abstract**

In this paper we study the *k*-means clustering problem. It
is well-known that the general version of this problem is NP-hard.
Numerous approximation algorithms have been proposed for this problem.
In this paper, we propose three constant approximation algorithms for
*k*-means clustering. The first algorithm runs in time
*Ο((k/ε) ^{k}nd)*, where

*k*is the number of clusters,

*n*is the size of input points, and

*d*is dimension of attributes. The second algorithm runs in time

*Ο(k*. This is the first algorithm for

^{3}n^{2}log n)*k*-means clustering that runs in time polynomial in

*n*,

*k*and

*d*simultaneously. The run time of the third algorithm

*Ο(k*is independent of

^{5}log^{3}kd)*n*. Though an algorithm whose run time is independent of

*n*is known for the

*k*-median problem, ours is the first such algorithm for the

*k*-means problem.

Download Paper (135 KB)