Fetching the paper…
Reading the bibliography…
We generalise the results of Bhattacharya et al.
Random sampling with a reservoir
J S Vitter · 1985
Earlier work this paper cites.
Applications of weighted Voronoi diagrams and randomization to variance-based
Mary Inaba, Naoki Katoh, and Hiroshi Imai · 1994
Earlier work this paper cites.
The geometry of graphs and some of its algorithmic applications
Nathan Linial, Eran London, and Yuri Rabinovich · 1995
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.
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
Earlier work this paper cites.
Clustering data streams: Theory and practice
Sudipto Guha, Adam Meyerson, Nina Mishra, Rajeev Motwani, and Liadan O’Callaghan · 2003
Earlier work this paper cites.
On coresets for
Sariel Har-Peled and Soham Mazumdar · 2004
Earlier work this paper cites.
Coresets in dynamic geometric data streams
Gereon Frahling and Christian Sohler · 2005
Earlier work this paper cites.
k k -means++: the advantages of careful seeding
David Arthur and Sergei Vassilvitskii · 2007
Earlier work this paper cites.
A PTAS for
Dan Feldman, Morteza Monemizadeh, and Christian Sohler · 2007
Earlier work this paper cites.
The hardness of
Sanjoy Dasgupta · 2008
Earlier work this paper cites.
Adaptive sampling for
Ankit Aggarwal, Amit Deshpande, and Ravi Kannan · 2009
Earlier work this paper cites.
Streaming
Nir Ailon, Ragesh Jaiswal, and Claire Monteleoni · 2009
Cited alongside, same era.
The hardness of k-means clustering in the plane
Andrea Vattani · 2009
Cited alongside, same era.
Stability yields a PTAS for
Pranjal Awasthi, Avrim Blum, and Or Sheffet · 2010
Cited alongside, same era.
Linear-time approximation schemes for clustering problems in any dimensions
Amit Kumar, Yogish Sabharwal, and Sandeep Sen · 2010
Cited alongside, same era.
Streaming k-means on well-clusterable data
Vladimir Braverman, Adam Meyerson, Rafail Ostrovsky, Alan Roytman, Michael Shindler, and Brian Tagiku · 2011
Cited alongside, same era.
The planar
Meena Mahajan, Prajakta Nimbhorkar, and Kasturi Varadarajan · 2012
Cited alongside, same era.
Clustering under approximation stability
Improved analysis of
Ragesh Jaiswal, Mehul Kumar, and Pulkit Yadav · 2015
Later among the works it cites.
Local search yields approximation schemes for
Vincent Cohen-Addad, Philip N. Klein, and Claire Mathieu · 2016
Later among the works it cites.
Local search yields a PTAS for
Zachary Friggstad, Mohsen Rezapour, and Mohammad R. Salavatipour · 2016
Later among the works it cites.
Better guarantees for k-means and euclidean k-median by primal-dual algorithms
S. Ahmadian, A. Norouzi-Fard, O. Svensson, and J. Ward · 2017
Later among the works it cites.
Training gaussian mixture models at scale via coresets
Mario Lucic, Matthew Faulkner, Andreas Krause, and Dan Feldman · 2017
Later among the works it cites.
Approximate Clustering with Same-Cluster Queries
Nir Ailon, Anup Bhattacharya, Ragesh Jaiswal, and Amit Kumar · 2018
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Maria-Florina Balcan, Avrim Blum, and Anupam Gupta · 2013
Cited alongside, same era.
Bico: Birch meets coresets for k-means clustering
Hendrik Fichtenberger, Marc Gillé, Melanie Schmidt, Chris Schwiegelshohn, and Christian Sohler · 2013
Cited alongside, same era.
The effectiveness of lloyd-type methods for the
Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman, and Chaitanya Swamy · 2013
Cited alongside, same era.
A simple
Ragesh Jaiswal, Amit Kumar, and Sandeep Sen · 2014
Cited alongside, same era.
The Hardness of Approximation of Euclidean
Pranjal Awasthi, Moses Charikar, Ravishankar Krishnaswamy, and Ali Kemal Sinop · 2015
Cited alongside, same era.
A unified framework for clustering constrained data without locality property
Hu Ding and Jinhui Xu · 2015
Cited alongside, same era.
Sampling in space restricted settings
Anup Bhattacharya, Davis Issac, Ragesh Jaiswal, and Amit Kumar · 2018
Later among the works it cites.
Faster algorithms for the constrained k-means problem
Anup Bhattacharya, Ragesh Jaiswal, and Amit Kumar · 2018
Later among the works it cites.
Semi-Supervised Algorithms for Approximately Optimal and Accurate Clustering
Buddhima Gamlath, Sangxia Huang, and Ola Svensson · 2018
Later among the works it cites.
Performance of johnson-lindenstrauss transform for k-means and k-medians clustering
Konstantin Makarychev, Yury Makarychev, and Ilya P. Razenshteyn · 2018
Later among the works it cites.
personal communication, July 2019
Sanjeev Khanna and Sepehr Assadi · 2019
Closest in time.
Fair coresets and streaming algorithms for fair k-means
Melanie Schmidt, Chris Schwiegelshohn, and Christian Sohler · 2020
Closest in time.