Clustering is difficult only when it does not matter

Amit Daniely, Nati Linial, Michael Saks

Numerous papers ask how difficult it is to cluster data. We suggest that the more relevant and interesting question is how difficult it is to cluster data sets {\em that can be clu…