G-2016-79
NP-hardness of balanced minimum sum-of-squares clustering
, , and
BibTeX referenceThe 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\).
Published October 2016 , 6 pages
Research Axis
Research applications
Publication
      
        Oct 2017
      
  
  
    
    , , and 
    
      Pattern Recognition Letters, 97, 44–45, 2017
      
        
        BibTeX reference