On the algorithmic complexity of a problem in cluster analysis
- 1 April 2011
- journal article
- Published by Pleiades Publishing Ltd in Journal of Applied and Industrial Mathematics
- Vol. 5 (2), 191-194
- https://doi.org/10.1134/s1990478911020050
Abstract
We prove that the MSSC problem (the problem of clustering the set of the vectors in the Euclidean space which minimizes the sum of squares) is NP-complete in the case when the dimension of the space is an input parameter of the problem, while the number of clusters is not an input parameter.Keywords
This publication has 5 references indexed in Scilit:
- NP-hardness of Euclidean sum-of-squares clusteringMachine Learning, 2009
- The Planar k-Means Problem is NP-HardLecture Notes in Computer Science, 2009
- Clustering Large Graphs via the Singular Value DecompositionMachine Learning, 2004
- Applications of weighted Voronoi diagrams and randomization to variance-based k-clusteringPublished by Association for Computing Machinery (ACM) ,1994
- Cluster Analysis and Mathematical ProgrammingJournal of the American Statistical Association, 1971