Hironori Takeuchi, Tetsuya Nasukawa, et al.
Transactions of the Japanese Society for Artificial Intelligence
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.
Hironori Takeuchi, Tetsuya Nasukawa, et al.
Transactions of the Japanese Society for Artificial Intelligence
Dzung Phan, Vinicius Lima
INFORMS 2023
Rangachari Anand, Kishan Mehrotra, et al.
IEEE Transactions on Neural Networks
Guo-Jun Qi, Charu Aggarwal, et al.
IEEE TPAMI