Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4950905 | Information Processing Letters | 2017 | 4 Pages |
Abstract
The k-means problem consists of finding k centers in Rd that minimize the sum of the squared distances of all points in an input set P from Rd to their closest respective center. Awasthi et al. recently showed that there exists a constant εâ²>0 such that it is NP-hard to approximate the k-means objective within a factor of 1+εâ². We establish that 1+εⲠis at least 1.0013.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Euiwoong Lee, Melanie Schmidt, John Wright,