On the Complexity of the Problem of Choice of Large Clusters

The paper considers the following problem. Given a set of Euclidean vectors, find severalclusters with a restriction on the maximum scatter of each cluster so that the size of the minimumcluster would be maximum. Here the scatter is the sum of squared distances from the clusterelements to its centroid. The NP-hardness of this problem is proved in the case where thedimension of the space is part of the input.