Retour

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.

, 18 pages

Axe de recherche

Application de recherche

Document

G-2007-50.pdf (160 Ko)