Merve Unuvar, Yurdaer Doganata, et al.
CLOUD 2014
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.
Merve Unuvar, Yurdaer Doganata, et al.
CLOUD 2014
Ronen Feldman, Martin Charles Golumbic
Ann. Math. Artif. Intell.
Hannaneh Hajishirzi, Julia Hockenmaier, et al.
UAI 2011
Joxan Jaffar
Journal of the ACM