On the k-Means/Median Cost Function

Approximate clustering via core-sets

Mihai Bādoiu, Sariel Har-Peled, and Piotr Indyk · 2002

Earlier work this paper cites.

Lectures on Discrete Geometry

Jiri Matousek · 2002

Earlier work this paper cites.

Intrinsic dimension estimation using packing numbers

Balázs Kégl · 2003

Earlier work this paper cites.

On coresets for k k -means and k k -median clustering

Sariel Har-Peled and Soham Mazumdar · 2004

Earlier work this paper cites.

Smaller coresets for k k -median and k k -means clustering

Sariel Har-Peled and Akash Kushal · 2005

Earlier work this paper cites.

Estimation of intrinsic dimensionality using high-rate vector quantization

Maxim Raginsky and Svetlana Lazebnik · 2006

Earlier work this paper cites.

k k -means++: the advantages of careful seeding

David Arthur and Sergei Vassilvitskii · 2007

Cited alongside, same era.

Adaptive sampling for k-means clustering

Ankit Aggarwal, Amit Deshpande, and Ravi Kannan · 2009

Cited alongside, same era.

Universal epsilon-approximators for integrals

Michael Langberg and Leonard J. Schulman · 2010

Cited alongside, same era.

A unified framework for approximating and clustering data

Dan Feldman and Michael Langberg · 2011

Cited alongside, same era.

Streamkm++: A clustering algorithm for data streams

Marcel R. Ackermann, Marcus Märtens, Christoph Raupach, Kamil Swierkot, Christiane Lammersen, and Christian Sohler · 2012

Cited alongside, same era.

Turning big data into tiny data: Constant-size coresets for k k -means, pca and projective clustering

Dan Feldman, Melanie Schmidt, and Christian Sohler · 2013

Cited alongside, same era.

Tight lower bound instances for k-means++ in two dimensions

Anup Bhattacharya, Ragesh Jaiswal, and Nir Ailon · 2016

Later among the works it cites.

Intrinsic dimension estimation: Advances and open problems

Francesco Camastra and Antonino Staiano · 2016

Later among the works it cites.

Accurate estimation of the intrinsic dimension using graph distances: Unraveling the geometric complexity of datasets

Daniele Granata and Vincenzo Carnevale · 2016

Later among the works it cites.

A constant-factor bi-criteria approximation guarantee for k k -means++

Dennis Wei · 2016

Later among the works it cites.

Improved guarantees for k-means++ and k-means++ parallel

Konstantin Makarychev, Aravind Reddy, and Liren Shan · 2020

Closest in time.

Fair coresets and streaming algorithms for fair k-means

Melanie Schmidt, Chris Schwiegelshohn, and Christian Sohler · 2020