A simple linear time ( 1+ ε)- approximation algorithm for geometric k-means clustering in any dimensions

Kumar, Amit ; Sabharwal, Yogish ; Sen, Sandeep (2004) A simple linear time ( 1+ ε)- approximation algorithm for geometric k-means clustering in any dimensions Proceedings - Annual Symposium on Foundations of Computer Science . pp. 454-462. ISSN 0272-5428

Preview

PDF - Author Version
118kB

Official URL: http://www.cse.iitd.ernet.in/~ssen/conf/focs04.pdf

Abstract

We present the first linear time (1+ε)-approximation algorithm for the k-means problem for fixed k and ε. Our algorithm runs in O(nd) time, which is linear in the size of the input. Another feature of our algorithm is its simplicity - the only technique involved is random sampling.

Item Type:	Article
Source:	Copyright of this article belongs to IEEE.
ID Code:	90261
Deposited On:	08 May 2012 14:36
Last Modified:	19 May 2016 04:31

Repository Staff Only: item control page