NP-hardness of Euclidean sum-of-squares clustering

作者：Daniel Aloise, Amit Deshpande, Pierre Hansen, Preyas Popat

摘要

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.

论文关键词：Clustering, Sum-of-squares, Complexity

论文评审过程：

论文官网地址：https://doi.org/10.1007/s10994-009-5103-0