Clustering Small Samples with Quality Guarantees: Adaptivity with One2all pps

Edith Cohen, Shiri Chechik, Haim Kaplan

Clustering of data points is a fundamental tool in data analysis. We consider points $X$ in a relaxed metric space, where the triangle inequality holds within a constant factor. Th…