Groupe d’études et de recherche en analyse des décisions


On the Complexity of Minimum Sum-of-Squares Clustering


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