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

Artem Pyatkin, Daniel Aloise, Nenad Mladenović

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)44-45
Number of pages2
JournalPattern Recognition Letters
Publication statusPublished - 1 Oct 2017


  • Balanced clustering
  • Complexity
  • Sum-of-squares


Dive into the research topics of 'NP-Hardness of balanced minimum sum-of-squares clustering'. Together they form a unique fingerprint.

Cite this