Back

G-2016-79

NP-hardness of balanced minimum sum-of-squares clustering

, , and

BibTeX reference

The balanced clustering problem consists of partitioning a set of \(n\) objects into \(K\) equal-sized clusters as long as \(n\) is a multiple of \(K\). A popular clustering criterion when the objects are points of a \(q\)-dimensional space is the minimum sum of squared distances from each point to the centroid of the cluster to which it belongs. We show in this paper that this problem is \(NP\)-hard in general dimension already for triplets, i.e., when \(n/K=3\).

, 6 pages

Research Axis

Research applications

Publication

, , and
Pattern Recognition Letters, 97, 44–45, 2017 BibTeX reference