Fetching the paper…
Reading the bibliography…
It is well known that most of the common clustering objectives are NP-hard to optimize.
Average case complete problems
Leonid A. Levin · 1986
Earlier work this paper cites.
On the theory of average case complexity
Shai Ben-David, Benny Chor, Oded Goldreich, and Michael Luby · 1989
Earlier work this paper cites.
Parameterized Complexity
Rodney G. Downey and M.R. Fellows · 1998
Earlier work this paper cites.
Efficient learning of linear perceptrons
Shai Ben-David and Hans-Ulrich Simon · 2000
Earlier work this paper cites.
Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time
Daniel A. Spielman and Shang-Hua Teng · 2001
Earlier work this paper cites.
Alternative measures of computational complexity with applications to agnostic learning
Shai Ben-David · 2006
Earlier work this paper cites.
The effectiveness of lloyd-type methods for the k-means problem
Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman, and Chaitanya Swamy · 2006
Earlier work this paper cites.
A framework for statistical clustering with constant time approximation algorithms for k
Shai Ben-David · 2007
Earlier work this paper cites.
Stability of k
Shai Ben-David, Dávid Pál, and Hans-Ulrich Simon · 2007
Earlier work this paper cites.
Clusterability: A theoretical study
Margareta Ackerman and Shai Ben-David · 2009
Cited alongside, same era.
Approximate clustering without the approximation
Maria-Florina Balcan, Avrim Blum, and Anupam Gupta · 2009
Cited alongside, same era.
Characterization of linkage-based clustering
Margareta Ackerman, Shai Ben-David, and David Loker · 2010
Cited alongside, same era.
Stability yields a ptas for k-median and k-means clustering
Pranjal Awasthi, Avrim Blum, and Or Sheffet · 2010
Cited alongside, same era.
Are stable instances easy?
Yonatan Bilu and Nathan Linial · 2010
Cited alongside, same era.
Stability and model selection in k
Ohad Shamir and Naftali Tishby · 2010
Cited alongside, same era.
Center-based clustering under perturbation stability
Are stable instances easy?
Yonatan Bilu and Nathan Linial · 2012
Later among the works it cites.
Clustering is difficult only when it does not matter
Amit Daniely, Nati Linial, and Michael Saks · 2012
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 · 2012
Later among the works it cites.
Data stability in clustering: A closer look
Lev Reyzin · 2012
Later among the works it cites.
Clustering under approximation stability
Maria-Florina Balcan, Avrim Blum, and Anupam Gupta · 2013
Later among the works it cites.
On the practically interesting instances of maxcut
Yonatan Bilu, Amit Daniely, Nati Linial, and Michael Saks · 2013
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Pranjal Awasthi, Avrim Blum, and Or Sheffet · 2012
Cited alongside, same era.
Clustering under perturbation resilience
Maria-Florina Balcan and Yingyu Liang · 2012
Cited alongside, same era.
Relax, no need to round: Integrality of clustering formulations
Pranjal Awasthi, Afonso Bandera, Moses Charikar, Ravishankar Krishnaswami, Soledad Voilar, and Rachel Ward · 2014
Later among the works it cites.
Data stability in clustering: A closer look
Shalev Ben-David and Lev Reyzin · 2014
Later among the works it cites.