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

G-2008-33

NP-Hardness of Euclidean Sum-of-Squares Clustering

, , et

A recent proof of NP-hardness of Euclidean sum-of-squares clustering, due to Drineas et al., Machine Learning 56, 9--33, 2004, is not valid. An alternate short proof is provided.

, 10 pages