Clustering under Perturbation Stability in Near-Linear Time

Pankaj K. Agarwal, Hsien-Chih Chang, Kamesh Munagala +2

We consider the problem of center-based clustering in low-dimensional Euclidean spaces under the perturbation stability assumption. An instance is $\alpha$-stable if the underlying opti…