NP-hardness of Euclidean sum-of-squares clustering

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.

Saved in:
Bibliographic Details
Published in:Machine learning 2009-05, Vol.75 (2), p.245-248
Main Authors: Aloise, Daniel, Deshpande, Amit, Hansen, Pierre, Popat, Preyas
Format: Article
Language:English
Subjects:
Applied sciences
Artificial Intelligence
Computer Science
Computer science
control theory
systems
Control
Euclidean space
Exact sciences and technology
Mechatronics
Natural Language Processing (NLP)
Robotics
Simulation and Modeling
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0885-6125
1573-0565
DOI:10.1007/s10994-009-5103-0