NP-Hardness of Quadratic Euclidean 1-Mean
and 1-Median 2-Clustering Problem
with Constraints on the Cluster Sizes
A. V. Kel’manova,b,*, A. V. Pyatkina,b,**, and V. I. Khandeeva,b,***
a Sobolev Institute of Mathematics, Siberian Branch,
Russian Academy of Sciences, Novosibirsk, 630090 Russia
b Novosibirsk State University, Novosibirsk, 630090 Russia
Correspondence to: *e-mail: kelm@math.nsc.ru
Correspondence to: **e-mail: artem@math.nsc.ru
Correspondence to: ***e-mail: khandeev@math.nsc.ru
Received 6 September, 2019
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.
DOI: 10.1134/S1064562419060127