Fetching the paper…
Reading the bibliography…
Motivated by the fact that distances between data points in many real-world clustering instances are often based on heuristic measures, Bilu and Linial~\cite{BL} proposed analyzing objective based clustering problems under the assumption that the optimum clustering to the objective is preserved under small multiplicative perturbations to distances between points.
V. N. Vapnik · 1998
Earlier work this paper cites.
Greedy strikes back: Improved facility location algorithms
S. Guha and S. Khuller · 1999
Earlier work this paper cites.
Approximating min-sum k-clustering in metric spaces
Y. Bartal, M. Charikar, and D. Raz · 2001
Earlier work this paper cites.
A constant-factor approximation algorithm for the k-median problem
M. Charikar, S. Guha, É. Tardos, and D. B. Shmoys · 2002
Earlier work this paper cites.
A new greedy approach for facility location problems
K. Jain, M. Mahdian, and A. Saberi · 2002
Earlier work this paper cites.
Learning with Kernels
B. Schölkopf and A. J. Smola · 2002
Earlier work this paper cites.
Approximation schemes for clustering problems
W. F. de la Vega, M. Karpinski, C. Kenyon, and Y. Rabani · 2003
Earlier work this paper cites.
Local search heuristics for k-median and facility location problems
V. Arya, N. Garg, R. Khandekar, A. Meyerson, K. Munagala, and V. Pandit · 2004
Earlier work this paper cites.
On stability properties of economic solution concepts
R. J. Lipton, E. Markakis, and A. Mehta · 2006
Earlier work this paper cites.
The effectiveness of lloyd-type methods for the k-means problem
R. Ostrovsky, Y. Rabani, L. J. Schulman, and C. Swamy · 2006
Earlier work this paper cites.
Smooth sensitivity and sampling in private data analysis
K. Nissim, S. Raskhodnikova, and A. Smith · 2007
Cited alongside, same era.
Differential privacy and robust statistics
C. Dwork and J. Lei · 2009
Cited alongside, same era.
Stability yields a ptas for k-median and k-means clustering
P. Awasthi, A. Blum, and O. Sheffet · 2010
Cited alongside, same era.
Approximate nash equilibria under stability conditions
M. F. Balcan and M. Braverman · 2010
Cited alongside, same era.
Robust hierarchical clustering
M. F. Balcan and P. Gupta · 2010
Cited alongside, same era.
Are stable instances easy?
Y. Bilu and N. Linial · 2010
Cited alongside, same era.
Center-based clustering under perturbation stability
P. Awasthi, A. Blum, and O. Sheffet · 2012
Closest in time.
Improved spectral-norm bounds for clustering
P. Awasthi and O. Sheffet · 2012
Closest in time.
Approximate clustering without the approximation
M.-F. Balcan, A. Blum, and A. Gupta · 2013
Closest in time.
On the practically interesting instances of maxcut
Y. Bilu, A. Daniely, N. Linial, and M. Saks · 2013
Closest in time.
Approximating k-median via pseudo-approximation
S. Li and O. Svensson · 2013
Closest in time.
Data stability in clustering: A closer look
L. Ben-David, Shalevand Reyzin · 2014
Closest in time.
Bilu-linial stable instances of max cut and minimum multiway cut
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Clustering with spectral norm and the k-means algorithm
A. Kumar and R. Kannan · 2010
Cited alongside, same era.
Hierarchical clustering with prototypes via minimax linkage
J. Bien and R. Tibshirani · 2011
Cited alongside, same era.
On the complexity of the metric tsp under stability considerations
M. Mihalák, M. Schöngens, R. Šrámek, and P. Widmayer · 2011
Cited alongside, same era.
K. Makarychev, Y. Makarychev, and A. Vijayaraghavan · 2014
Closest in time.
Constant factor approximation for balanced cut in the pie model
K. Makarychev, Y. Makarychev, and A. Vijayaraghavan · 2014
Closest in time.
M.-F. Balcan, N. Haghtalab, and C. White · 2015
Closest in time.