Kenneth L. Clarkson, Elad Hazan, et al.
Journal of the ACM
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.
Kenneth L. Clarkson, Elad Hazan, et al.
Journal of the ACM
Yale Song, Zhen Wen, et al.
IJCAI 2013
Imran Nasim, Melanie Weber
SCML 2024
Amarachi Blessing Mbakwe, Joy Wu, et al.
NeurIPS 2023