Deterministic Clustering in High Dimensional Spaces: Sketches and Approximation

parameter ε or k. Furthermore, there is no coreset construction that succeeds with probability 1−1/n and whose size does not depend on the number of input points, n. This has led researchers in the [...] stands in sharp contrast with the (1+ε)-approximation achievable in that case, when allowing randomization. In this talk, we discuss [...] are close to the best-known randomized ones. We also show a deterministic algorithm for computing a (1+ε)-approximation to k-median and k-means in high dimensional Euclidean spaces in time 2^(k^2/ε^O(1) …