Fetching the paper…
Reading the bibliography…
The Euclidean $k$-means problem is a classical problem that has been extensively studied in the theoretical computer science, machine learning and the computational geometry communities.
Least squares quantization in PCM
S.P. Lloyd · 1982
Earlier work this paper cites.
A unified approach to approximation algorithms for bottleneck problems
Dorit S Hochbaum and David B Shmoys · 1986
Earlier work this paper cites.
Optimal algorithms for approximate clustering
Tomás Feder and Daniel Greene · 1988
Earlier work this paper cites.
Ramanujan graphs
A. Lubotzky, R. Phillips, and P. Sarnak · 1988
Earlier work this paper cites.
Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
Noga Alon, Jehoshua Bruck, Joseph Naor, Moni Naor, and Ron M Roth · 1992
Earlier work this paper cites.
Existence and explicit constructions of q + 1 regular ramanujan graphs for every prime power q
M. Morgenstern · 1994
Earlier work this paper cites.
Approximation schemes for Euclidean
S. Arora, P. Raghavan, and S. Rao · 1999
Earlier work this paper cites.
A constant-factor approximation algorithm for the k-median problem
M. Charikar, S. Guha, E. Tardos, and D. B. Shmoy · 1999
Earlier work this paper cites.
A nearly linear-time approximation scheme for the euclidean k-median problem
Stavros G Kolliopoulos and Satish Rao · 1999
Earlier work this paper cites.
On approximate geometric k-clustering
Jiri Matoušek · 2000
Earlier work this paper cites.
Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation
K. Jain and V. V. Vazirani · 2001
Earlier work this paper cites.
Approximate clustering via core-sets
Mihai Bādoiu, Sariel Har-Peled, and Piotr Indyk · 2002
Earlier work this paper cites.
A new greedy approach for facility location problems
K. Jain, M. Mahdian, and A. Saberi · 2002
Cited alongside, same era.
A local search approximation algorithm for k-means clustering
Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, and Angela Y. Wu · 2002
Cited alongside, same era.
An elementary proof of a theorem of johnson and lindenstrauss
Sanjoy Dasgupta and Anupam Gupta · 2003
Cited alongside, same era.
Approximation schemes for clustering problems
W. Fernandez de la Vega, Marek Karpinski, Claire Kenyon, and Yuval Rabani · 2003
Cited alongside, same era.
Embeddings and non-approximability of geometric problems
Venkatesan Guruswami and Piotr Indyk · 2003
Cited alongside, same era.
The probabilistic method
Noga Alon and Joel H Spencer · 2004
Cited alongside, same era.
A ptas for k-means clustering based on weak coresets
Dan Feldman, Morteza Monemizadeh, and Christian Sohler · 2007
Later among the works it cites.
The hardness of k-means clustering
S. Dasgupta · 2008
Later among the works it cites.
Vertex cover might be hard to approximate to within 2-
Subhash Khot and Oded Regev · 2008
Later among the works it cites.
Approximating maximum subgraphs without short cycles
Guy Kortsarz, Michael Langberg, and Zeev Nutov · 2008
Later among the works it cites.
The top ten algorithms in data mining
X. Wu, V. Kumar, J. Ross Quinlan, J. Ghosh, Q. Yang, H. Motoda, G. J. McLachlan, A. Ng, B. Liu, P. S. Yu, Z.-H. Zhou, M. Steinbach, D. J. Hand, and D. Steinberg · 2008
Later among the works it cites.
NP-hardness of Euclidean sum-of-squares clustering
Daniel Aloise, Amit Deshpande, Pierre Hansen, and Preyas Popat · 2009
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Local search heuristics for k-median and facility location problems
V. Arya, N. Garg, R. Khandekar, A. Meyerson, K. Munagala, and V. Pandit · 2004
Cited alongside, same era.
A simple linear time
A. Kumar, Y. Sabharwal, and S. Sen · 2004
Cited alongside, same era.
On the hardness of approximating minimum vertex cover
Irit Dinur and Samuel Safra · 2005
Cited alongside, same era.
The effectiveness of lloyd-type methods for the k-means problem
R. Ostrovsky, Y. Rabani, L. Schulman, and C. Swamy · 2006
Cited alongside, same era.
k-means++: the advantages of careful seeding
David Arthur and Sergei Vassilvitskii · 2007
Cited alongside, same era.
Approximate clustering without the approximation
M.-F. Balcan, A. Blum, and A. Gupta · 2009
Later among the works it cites.
The planar k-means problem is np-hard
Meena Mahajan, Prajakta Nimbhorkar, and Kasturi Varadarajan · 2009
Later among the works it cites.
Clustering with spectral norm and the
A. Kumar and R. Kannan · 2010
Later among the works it cites.
Approximating k-median via pseudo-approximation
Shi Li and Ola Svensson · 2013
Later among the works it cites.
An improved approximation for $k$-median, and positive correlation in budgeted optimization
Jaroslaw Byrka, Thomas Pensyl, Bartosz Rybicki, Aravind Srinivasan, and Khoa Trinh · 2014
Later among the works it cites.