On the algorithmic complexity of a problem in cluster analysis

Abstract

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.