NP-hardness of Euclidean sum-of-squares clustering
A recent proof of NP-hardness of Euclidean sum-of-squares clustering, due to Drineas et al. (Mach. Learn. 56:9-33, 2004), is not valid. An alternate short proof is provided.
sum-of-squares clustering complexity