2015/10/19 by Shai Ben-David, Ben-David, Shai
Computer Science · Mathematics · #Advanced Database Systems and Queries #Algorithms and Data Compression #Data Management and Algorithms #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #cs.LG #stat.ML
paper · pdf · doi:10.48550/arxiv.1510.05336
5 pages
arxiv created 2015/10/19 · openalex publication_date 2015/10/19 · arxiv updated 2015/10/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
It is well known that most of the common clustering objectives are NP-hard to optimize. In practice, however, clustering is being routinely carried out. One approach for providing theoretical understanding of this seeming discrepancy is to come up with notions of clusterability that distinguish realistically interesting input data from worst-case data sets. The hope is that there will be clustering algorithms that are provably efficient on such "clusterable" instances. This paper addresses the thesis that the computational hardness of clustering tasks goes away for inputs that one really cares about. In other words, that "Clustering is difficult only when it does not matter" (the CDNM thesis for short). I wish to present a a critical bird's eye overview of the results published on this issue so far and to call attention to the gap between available and desirable results on this issue. A longer, more detailed version of this note is available as arXiv:1507.05307. I discuss which requirements should be met in order to provide formal support to the the CDNM thesis and then examine existing results in view of these requirements and list some significant unsolved research challenges in that direction.