An exact pseudopolynomial algorithm for a problem of the two-cluster partitioning of a set of vectors
Alexander V. Kel’manov, ВЛАДИМИР ИЛЬИЧ ХАНДЕЕВ · Journal of Applied and Industrial Mathematics · 2015
We consider the strongly NP-hard problem of partitioning a set of Euclidean vectors into two clusters of given sizes so as to minimize the sum of the squared distances from the elements of the clusters to their centers. It is assumed that the center of one of the clusters is unknown and determined as the average value over all vectors in the cluster. The center of the other cluster is the origin.We prove that, for a fixed dimension of the space, the problem is solvable in polynomial time. We also present and justify an exact pseudopolynomial algorithm in the case of integer components of the vectors.