Fetching the paper…
Reading the bibliography…
The most well known and ubiquitous clustering problem encountered in nearly every branch of science is undoubtedly $k$-means: given a set of data points and a parameter $k$, select $k$ centres and partition the data points into $k$ clusters around these centres so that the sum of squares of distances of the points to their cluster centre is minimized.
Applications of weighted Voronoi diagrams and randomization to variance-based K-clustering
Mary Inaba, Naoki Katoh, and Hiroshi Imai · 1994
Earlier work this paper cites.
Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
Sanjeev Arora · 1998
Earlier work this paper cites.
Approximation schemes for Euclidean K-medians and related problems
Sanjeev Arora, Prabhakar Raghavan, and Satish Rao · 1998
Earlier work this paper cites.
A nearly linear-time approximation scheme for the Euclidean Kappa-median problem
Stavros G. Kolliopoulos and Satish Rao · 1999
Earlier work this paper cites.
On approximate geometric k-clustering
Jirı Matoušek · 2000
Earlier work this paper cites.
Local search heuristic for K-median and facility location problems
Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, and Vinayaka Pandit · 2001
Earlier work this paper cites.
Approximate clustering via Coresets
Mihai Bādoiu, Sariel Har-Peled, and Piotr Indyk · 2002
Earlier work this paper cites.
Polynomial-Time Approximation Schemes for geometric min-sum median clustering
Rafail Ostrovsky and Yuval Rabani · 2002
Earlier work this paper cites.
How fast is K-means?
Sanjoy Dasgupta · 2003
Earlier work this paper cites.
Approximation schemes for clustering problems
W. Fernandez de la Vega, Marek Karpinski, Claire Kenyon, and Yuval Rabani · 2003
Earlier work this paper cites.
A tight bound on approximating arbitrary metrics by tree metrics
Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar · 2003
Earlier work this paper cites.
Local search heuristics for K-median and facility location problems
Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, and Vinayaka Pandit · 2004
Earlier work this paper cites.
Clustering large graphs via the singular value decomposition
P. Drineas, A. Frieze, R. Kannan, S. Vempala, and V. Vinay · 2004
Earlier work this paper cites.
On Coresets for K-means and K-median clustering
Sariel Har-Peled and Soham Mazumdar · 2004
Earlier work this paper cites.
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 · 2004
Earlier work this paper cites.
A simple linear time (1+ ϵ \epsilon ) -approximation algorithm for K-means clustering in any dimensions
Amit Kumar, Yogish Sabharwal, and Sandeep Sen · 2004
Earlier work this paper cites.
Bypassing the embedding: Algorithms for low dimensional metrics
Kunal Talwar · 2004
Earlier work this paper cites.
How does gene expression clustering work?
Patrik D’haeseleer et al · 2005
Cited alongside, same era.
Smaller Coresets for K-median and K-means clustering
Sariel Har-Peled and Akash Kushal · 2005
Cited alongside, same era.
How fast is the K-means method?
Sariel Har-Peled and Bardia Sadri · 2005
Cited alongside, same era.
How slow is the K-means method?
David Arthur and Sergei Vassilvitskii · 2006
Cited alongside, same era.
Least squares quantization in pcm
S. Lloyd · 2006
Cited alongside, same era.
K-means++: The advantages of careful seeding
David Arthur and Sergei Vassilvitskii · 2007
Cited alongside, same era.
A PTAS for K-means clustering based on weak Coresets
Dan Feldman, Morteza Monemizadeh, and Christian Sohler · 2007
Smoothed analysis of the K-means method
David Arthur, Bodo Manthey, and Heiko Röglin · 2011
Later among the works it cites.
A 1.488-approximation for the uncapacitated facility location problem
Shi Li · 2011
Later among the works it cites.
K-means requires exponentially many iterations even in the plane
Andrea Vattani · 2011
Later among the works it cites.
Turning big data into tiny data: Constant-size Coresets for K-means, PCA and projective clustering
Dan Feldman, Melanie Schmidt, and Christian Sohler · 2013
Later among the works it cites.
Network-based stratification of tumor mutations
Matan Hofree, John P Shen, Hannah Carter, Andrew Gross, and Trey Ideker · 2013
Later among the works it cites.
Approximating K-median via pseudo-approximation
Shi Li and Ola Svensson · 2013
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Simpler analyses of local search algorithms for facility location
A. Gupta and T. Tangwongsan · 2008
Cited alongside, same era.
NP-hardness of Euclidean sum-of-squares clustering
Daniel Aloise, Amit Deshpande, Pierre Hansen, and Preyas Popat · 2009
Cited alongside, same era.
On Coresets for K-median and K-means clustering in metric and Euclidean spaces and their applications
Ke Chen · 2009
Cited alongside, same era.
The planar K-means problem is NP-hard
Meena Mahajan, Prajakta Nimbhorkar, and Kasturi Varadarajan · 2009
Cited alongside, same era.
The hardness of K-means clustering in the plane
Andrea Vattani · 2009
Cited alongside, same era.
Later among the works it cites.
The effectiveness of Lloyd-type methods for the K-means problem
Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman, and Chaitanya Swamy · 2013
Later among the works it cites.
The Hardness of Approximation of Euclidean K-Means
Pranjal Awasthi, Moses Charikar, Ravishankar Krishnaswamy, and Ali Kemal Sinop · 2015
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 · 2015
Later among the works it cites.
Effectiveness of local search for geometric optimization
Vincent Cohen-Addad and Claire Mathieu · 2015
Later among the works it cites.
Effectiveness of local search for geometric optimization
Vincent Cohen-Addad and Claire Mathieu · 2015
Later among the works it cites.
On variants of K-means clustering
Sayan Bandyapadhyay and Kasturi Varadarajan · 2016
Closest in time.
Theoretical analysis of the K-means algorithm - A survey
Johannes Blömer, Christiane Lammersen, Melanie Schmidt, and Christian Sohler · 2016
Closest in time.
Local search yields approximation schemes for k-means and k-median in euclidean and minor-free metrics
Vincent Cohen-Addad, Philip N. Klein, and Claire Mathieu · 2016
Closest in time.
The power of local search for clustering
Vincent Cohen-Addad, Philip N. Klein, and Claire Mathieu · 2016
Closest in time.
Local search yields a ptas for k-means in doubling metrics
Zachary Friggstad, Mohsen Rezapour, and Mohammad R. Salavatipour · 2016
Closest in time.
Local search yields a PTAS for k-means in doubling metrics
Zachary Friggstad, Mohsen Rezapour, and Mohammad R. Salavatipour · 2016
Closest in time.