Konstantin Voevodski

Large Scale K-Median Clustering for Stable Clustering Instances

We study the problem of computing a good k-median clustering in a parallel computing environment. We design an efficient algorithm that gives a constant-factor approximation to the optimal solution for stable clustering instances. The notion of stability that we consider is resilience to perturbatio…