Header menu link for other important links
X
Linear-time approximation schemes for clustering problems in any dimensions
A. Kumar, Y. Sabharwal,
Published in
2010
Volume: 57
   
Issue: 2
Abstract
We present a general approach for designing approximation algorithms for a fundamental class of geometric clustering problems in arbitrary dimensions. More specifically, our approach leads to simple randomized algorithms for the k-means, k-median and discrete k-means problems that yield (1+ε) approximations with probability ≥ 1/2 and running times of O(2(k/ε)O(1)dn). These are the first algorithms for these problems whose running times are linear in the size of the input (nd for n points in d dimensions) assuming k and ε are fixed. Our method is general enough to be applicable to clustering problems satisfying certain simple properties and is likely to have further applications. © 2010 ACM.
About the journal
Published in
Open Access
Impact factor
N/A