Fetching the paper…
Reading the bibliography…
In this work, we study the $k$-median and $k$-means clustering problems when the data is distributed across many servers and can contain outliers.
Clustering to minimize the maximum intercluster distance
Teofilo F Gonzalez · 1985
Earlier work this paper cites.
On the distributional complexity of disjointness
Alexander A. Razborov · 1992
Earlier work this paper cites.
A constant-factor approximation algorithm for the k-median problem
Moses Charikar, Sudipto Guha, Éva Tardos, and David B Shmoys · 1999
Earlier work this paper cites.
Algorithms for facility location problems with outliers
Moses Charikar, Samir Khuller, David M Mount, and Giri Narasimhan · 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.
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.
An information statistics approach to data stream and communication complexity
Ziv Bar-Yossef, Thathachar S Jayram, Ravi Kumar, and D Sivakumar · 2004
Earlier work this paper cites.
Achieving anonymity via clustering
Gagan Aggarwal, Tomás Feder, Krishnaram Kenthapadi, Samir Khuller, Rina Panigrahy, Dilys Thomas, and An Zhu · 2006
Earlier work this paper cites.
A discriminative framework for clustering via similarity functions
Maria-Florina Balcan, Avrim Blum, and Santosh Vempala · 2008
Earlier work this paper cites.
A constant factor approximation algorithm for k-median clustering with outliers
Ke Chen · 2008
Earlier work this paper cites.
Clusterability: A theoretical study
Margareta Ackerman and Shai Ben-David · 2009
Earlier work this paper cites.
Finding low error clusterings
Maria-Florina Balcan and Mark Braverman · 2009
Earlier work this paper cites.
Agnostic clustering
Maria-Florina Balcan, Heiko Röglin, and Shang-Hua Teng · 2009
Earlier work this paper cites.
On nash-equilibria of approximation-stable games
Pranjal Awasthi, Maria-Florina Balcan, Avrim Blum, Or Sheffet, and Santosh Vempala · 2010
Earlier work this paper cites.
Clustering with spectral norm and the k-means algorithm
Amit Kumar and Ravindran Kannan · 2010
Earlier work this paper cites.
Ncbi reference sequences (refseq): current status, new features and genome annotation policy
Kim D Pruitt, Tatiana Tatusova, Garth R Brown, and Donna R Maglott · 2011
Earlier work this paper cites.
Min-sum clustering of protein sequences with limited distance information
Konstantin Voevodski, Maria-Florina Balcan, Heiko Röglin, Shang-Hua Teng, and Yu Xia · 2011
Cited alongside, same era.
Center-based clustering under perturbation stability
Pranjal Awasthi, Avrim Blum, and Or Sheffet · 2012
Cited alongside, same era.
Improved spectral-norm bounds for clustering
Pranjal Awasthi and Or Sheffet · 2012
Cited alongside, same era.
Are stable instances easy?
Yonatan Bilu and Nathan Linial · 2012
Cited alongside, same era.
The effectiveness of lloyd-type methods for the k-means problem
Rafail Ostrovsky, Yuval Rabani, Leonard J Schulman, and Chaitanya Swamy · 2012
Cited alongside, same era.
Clustering under approximation stability
Maria-Florina Balcan, Avrim Blum, and Anupam Gupta · 2013
Fast distributed k-center clustering with outliers on massive data
Gustavo Malkomes, Matt J Kusner, Wenlin Chen, Kilian Q Weinberger, and Benjamin Moseley · 2015
Later among the works it cites.
Better guarantees for k-means and euclidean k-median by primal-dual algorithms
Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, and Justin Ward · 2016
Later among the works it cites.
Approximation algorithms for clustering problems with lower bounds and outliers
Sara Ahmadian and Chaitanya Swamy · 2016
Later among the works it cites.
k k -center clustering under perturbation resilience
Maria-Florina Balcan, Nika Haghtalab, and Colin White · 2016
Later among the works it cites.
Clustering under perturbation resilience
Maria Florina Balcan and Yingyu Liang · 2016
Later among the works it cites.
Communication-optimal distributed clustering
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Distributed k k -means and k k -median clustering on general topologies
Maria-Florina F Balcan, Steven Ehrlich, and Yingyu Liang · 2013
Cited alongside, same era.
A tight bound for set disjointness in the message-passing model
Mark Braverman, Faith Ellen, Rotem Oshman, Toniann Pitassi, and Vinod Vaikuntanathan · 2013
Cited alongside, same era.
Center based clustering: A foundational perspective
Pranjal Awasthi and Maria-Florina Balcan · 2014
Cited alongside, same era.
Distributed balanced clustering via mapping coresets
Mohammadhossein Bateni, Aditya Bhaskara, Silvio Lattanzi, and Vahab Mirrokni · 2014
Cited alongside, same era.
Decompositions of triangle-dense graphs
Rishi Gupta, Tim Roughgarden, and C Seshadhri · 2014
Cited alongside, same era.
k-means++ under approximation stability
Manu Agarwal, Ragesh Jaiswal, and Arindam Pal · 2015
Cited alongside, same era.
Jiecao Chen, He Sun, David Woodruff, and Qin Zhang · 2016
Later among the works it cites.
A bi-criteria approximation algorithm for k k means
Konstantin Makarychev, Yury Makarychev, Maxim Sviridenko, and Justin Ward · 2016
Later among the works it cites.
General and robust communication-efficient algorithms for distributed clustering
Pranjal Awasthi, Maria-Florina Balcan, and Colin White · 2017
Closest in time.
Algorithms for stable and perturbation–resilient problems
Haris Angelidakis, Konstantin Makarychev, and Yury Makarychev · 2017
Closest in time.
Data driven resource allocation for distributed learning
Travis Dick, Mu Li, Venkata Krishna Pillutla, Colin White, Maria Florina Balcan, and Alex Smola · 2017
Closest in time.
Distributed partial clustering
Sudipto Guha, Yi Li, and Qin Zhang · 2017
Closest in time.
Constant approximation for k-median and k-means with outliers via iterative rounding
Ravishankar Krishnaswamy, Shi Li, and Sai Sandeep · 2017
Closest in time.
A hierarchical algorithm for extreme clustering
Ari Kobren, Nicholas Monath, Akshay Krishnamurthy, and Andrew McCallum · 2017
Closest in time.
Perturbation resilient clustering for k k -center and related problems via lp relaxations
Chandra Chekuri and Shalmoli Gupta · 2018
Closest in time.
Distributed k k -clustering for data with heavy noise
Shi Li and Xiangyu Guo · 2018
Closest in time.