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.
Published July 2007 , 18 pages
G-2007-50.pdf (200 KB)