NP-hardness of quadratic Euclidean 1-Mean and 1-Median 2-Clustering problem with the constraints on the cluster sizes
Alexander V. Kel’manov, A. V. Pyatkin, ВЛАДИМИР ИЛЬИЧ ХАНДЕЕВ · Доклады Академии наук · 2019
In the paper, we consider a problem of clustering a finite set of N points in d-dimensional Euclidean space into two clusters minimizing the sum over all clusters of the intracluster sums of the distances between clusters elements and their centers. The center of one cluster is defined as centroid (geometric center). The center of the other one is a sought point in the input set. We analyze the variant of the problem with the given clusters sizes. We have proved the strong NP-hardness of this problem.