Polynomial-time approximation scheme for a problem of partitioning a finite set into two clusters

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 defined as the mean value over all elements in this cluster. A polynomial-time approximation scheme (PTAS) is provided.