Linear time algorithms for clustering problems in any dimensions

Kumar, Amit ; Sabharwal, Yogish ; Sen, Sandeep (2005) Linear time algorithms for clustering problems in any dimensions International Colloquium on Automata, Languages and Programming . pp. 1374-1385.

Full text not available from this repository.


We generalize the k-means algorithm presented by the authors [14] and show that the resulting algorithm can solve a larger class of clustering problems that satisfy certain properties (existence of a random sampling procedure and tightness). We prove these properties for the k-median and the discrete k-means clustering problems, resulting in O(2 (k/ε)O(1) dn) time (1 + ε)-approximation algorithms for these problems. These are the first algorithms for these problems linear in the size of the input (nd for n points in d dimensions), independent of dimensions in the exponent, assuming k and ε to be fixed. A key ingredient of the k-median result is a (1 + ε)-approximation algorithm for the 1-median problem which has running time O(2 (1/ε)O(1) d). The previous best known algorithm for this problem had linear running time.

Item Type:Article
Source:Copyright of this article belongs to European Association for Theoretical Computer Science (EATCS).
ID Code:90264
Deposited On:25 Jun 2012 13:37
Last Modified:25 Jun 2012 13:37

Repository Staff Only: item control page