On the algorithmic complexity of a problem in cluster analysis
A. V. Dolgushev, Alexander V. Kel’manov · Journal of Applied and Industrial Mathematics · 2011
We prove that the MSSC problem (the problem of clustering the set of the vectors in the Euclidean space which minimizes the sum of squares) is NP-complete in the case when the dimension of the space is an input parameter of the problem, while the number of clusters is not an input parameter.