NP-Completeness of Some Problems of Partitioning a Finite Set of Points in Euclidean Space into Balanced Clusters
Alexander V. Kel’manov, A. V. Pyatkin, ВЛАДИМИР ИЛЬИЧ ХАНДЕЕВ · Doklady Mathematics · 2019
Abstract We consider three related problems of partitioning an $$N$$-element set of points in $$d$$-dimensional Euclidean space into two clusters balancing the value of (1) the intracluster quadratic variance normalized by the cluster size in the first problem; (2) the intracluster quadratic variance in the second problem; and (3) the size-weighted intracluster quadratic variance in the third problem. The NP-completeness of all these problems is proved.