Query K-means Clustering and the Double Dixie Cup Problem

I Chien, Chao Pan, Olgica Milenkovic

We consider the problem of approximate $K$-means clustering with outliers and side information provided by same-cluster queries and possibly noisy answers. Our solution shows that,…