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
Imran Nasim, Melanie Weber
SCML 2024
Annina Riedhauser, Viacheslav Snigirev, et al.
CLEO 2023
Ankit Vishnubhotla, Charlotte Loh, et al.
NeurIPS 2023