Improved and simplified inapproximability for k-means

详细信息    查看全文

• 作者：Euiwoong Lee¹ ; Melanie Schmidt ; ² ; ^{melanie.schmidt@tu-dortmund.de} ; John Wright³
• 关键词：k-Means ; Hardness of approximation ; Clustering ; Computational complexity
• 刊名：Information Processing Letters
• 出版年：2017
• 出版时间：April 2017
• 年：2017
• 卷：120
• 期：Complete
• 页码：40-43
• 全文大小：219 K
• 卷排序：120

文摘

It is NP-hard to approximate the k-means problem within a factor of 1.0013. Previously, Awasthi et al. proved APX-hardness for an unknown and very small constant. The proof is based on their work, but greatly simplified.