Authors: Pyatkin, Artem
Aloise, Daniel
Mladenović, Nenad 
Title: NP-Hardness of balanced minimum sum-of-squares clustering
Journal: Pattern Recognition Letters
Volume: 97
First page: 44
Last page: 45
Issue Date: 1-Oct-2017
Rank: M22
ISSN: 0167-8655
DOI: 10.1016/j.patrec.2017.05.033
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.
Keywords: Balanced clustering | Complexity | Sum-of-squares
Publisher: Elsevier
Project: RFBR, projects 16-07-00168 and 15-01-00462
RSF grant 14-41-00039
CNPq/Brazil grants 308887/2014-0 and 400350/2014-9

Show full item record


checked on May 22, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.