Improved and Simplified Inapproximability for k-means

Stuart P. Lloyd, Least squares quantization in PCM , Bell Laboratories Technical Memorandum (1957), later published as [ Llo82 ]

1957

Earlier work this paper cites.

Mary Inaba, Naoki Katoh, and Hiroshi Imai, Applications of weighted voronoi diagrams and randomization to variance-based k-clustering (extended abstract) , Proceedings of the 10th ACM Symposium on Computational Geometry (SoCG, 1994, pp. 332–339

1994

Earlier work this paper cites.

Kamal Jain and Vijay V. Vazirani, Approximation algorithms for metric facility location and k k -median problems using the primal-dual schema and lagrangian relaxation , Journal of the ACM 48

2001

Earlier work this paper cites.

Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, and Angela Y. Wu, A local search approximation algorithm for k k -means clustering , Computational Geometry 28

2004

Earlier work this paper cites.

Irit Dinur and Samuel Safra, On the hardness of approximating minimum vertex cover , Annals of Mathematics (2005), 439–485

2005

Cited alongside, same era.

Michael Mitzenmacher and Eli Upfal, Probability and computing – randomized algorithms and probabilistic analysis , Cambridge University Press, 2005, Theorem 6.3 on p. 129 in Chapter 6

Original

2005

Cited alongside, same era.

Miroslav Chlebík and Janka Chlebíková, Complexity of approximating bounded variants of optimization problems , Theoretical Computer Science 354

2006

Cited alongside, same era.

Sanjoy Dasgupta, The hardness of k k -means clustering , Tech. Report CS2008-0916, University of California, 2008

2008

Cited alongside, same era.

Daniel Aloise, Amit Deshpande, Pierre Hansen, and Preyas Popat, NP-hardness of Euclidean sum-of-squares clustering , Machine Learning 75

2009

Later among the works it cites.

Meena Mahajan, Prajakta Nimbhorkar, and Kasturi R. Varadarajan, The Planar k k -means Problem is NP-Hard , Proceedings of the 3rd Workshop on Algorithms and Computation (WALCOM), 2009, pp. 274 – 285

2009

Later among the works it cites.

Dan Feldman and Michael Langberg, A unified framework for approximating and clustering data , Proceedings of the 43th ACM Symposium on the Theory of Computing (STOC), 2011, pp. 569 – 578

2011

Later among the works it cites.

Pranjal Awasthi, Moses Charikar, Ravishankar Krishnaswamy, and Ali Kemal Sinop, The hardness of approximation of euclidean k-means , SoCG 2015 (accepted), 2015

2015

Closest in time.