Back

G-2007-50

On the Complexity of Minimum Sum-of-Squares Clustering

and

BibTeX reference

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

Research Axis

Research application

Document

G-2007-50.pdf (200 KB)