Abstract:
We consider the strongly $NP$-hard problem of partitioning a finite set of points of Euclidean space into two clusters of given cardinalities under the minimum criterion for the sum over the clusters of the intracluster sums of squared distances from elements of the cluster to its center. It is assumed that the center of one of the clusters is given (without loss of generality, at the origin). The center of the second cluster is unknown and is determined as the mean value over all elements in this cluster. A polynomial-time approximation scheme (PTAS) is provided.