ML Anthology

NP-Hardness of Euclidean Sum-of-Squares Clustering

Daniel Aloise, Amit Deshpande, Pierre Hansen, Preyas Popat
MLJ 2009 pp. 245-248
doi:10.1007/S10994-009-5103-0 /mlj/2009/aloise2009mlj-nphardness/

Abstract

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.

PDF MLJ Semantic Scholar

Cite

Text

Aloise et al. "NP-Hardness of Euclidean Sum-of-Squares Clustering." Machine Learning, 2009. doi:10.1007/S10994-009-5103-0

Markdown

[Aloise et al. "NP-Hardness of Euclidean Sum-of-Squares Clustering." Machine Learning, 2009.](https://mlanthology.org/mlj/2009/aloise2009mlj-nphardness/) doi:10.1007/S10994-009-5103-0

BibTeX

@article{aloise2009mlj-nphardness,
  title     = {{NP-Hardness of Euclidean Sum-of-Squares Clustering}},
  author    = {Aloise, Daniel and Deshpande, Amit and Hansen, Pierre and Popat, Preyas},
  journal   = {Machine Learning},
  year      = {2009},
  pages     = {245-248},
  doi       = {10.1007/S10994-009-5103-0},
  volume    = {75},
  url       = {https://mlanthology.org/mlj/2009/aloise2009mlj-nphardness/}
}