NP-hardness of Euclidean sum-of-squares clustering

AloiseDaniel,DeshpandeAmit,HansenPierre,PopatPreyas

NP-hardness of Euclidean sum-of-squares clustering

2009

AloiseDaniel
DeshpandeAmit
HansenPierre
PopatPreyas

A recent proof of NP-hardness of Euclidean sum-of-squares clustering, due to Drineas et al. (Mach. Learn. 56:9---33, 2004), is not valid. An alternate short proof is provided.

Keywords:

Euclidean geometry
Mach number
Discrete mathematics
Pattern recognition
Cluster analysis
Mathematics
Explained sum of squares
Artificial intelligence

Correction
Source
Cite
Save
Machine Reading By IdeaReader

References

Citations