Adversarially Robust Streaming Algorithms for $(k,z)$-Clustering

Chengzhi Guo, Shaofeng H. C. Jiang, Robert Krauthgamer +3

We design adversarially robust algorithms for dynamic geometric streams that $(1+\epsilon )$-approximate $k$-Median and $k$-Means in Euclidean space ${\mathbb{R}}^d$, using $\tilde{O}(kd \…