NP-Hardness of Quadratic Euclidean 1-Mean and 1-Median 2-Clustering Problem with Constraints on the Cluster Sizes

Abstract

We consider the problem of clustering a finite set of N points in d-dimensional Euclidean space into two clusters minimizing the sum (over both clusters) of the intracluster sums of the squared distances between the cluster elements and their centers. The center of one cluster is defined as a centroid (geometric center). The center of the other cluster is determined as an optimized point in the input set. We analyze the variant of the problem with given cluster sizes such that their sum is equal to the size of the input set. The strong NP-hardness of this problem is proved.