G-2007-50
On the Complexity of Minimum Sum-of-Squares Clustering
et référence BibTeX
To the best of our knowledge, the complexity of minimum sum-of-squares clustering is unknown. Yet, it has often been stated that this problem is NP-hard. We examine causes for such confusion and in the process show that a recent proof of Drineas et al. in Machine Learning 56, 9-33, 2004 is not valid and unlikely to be salvaged.
Paru en juillet 2007 , 18 pages
Axe de recherche
Application de recherche
Document
G-2007-50.pdf (160 Ko)