  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. The hope is
that by exploiting the structure in such instances, one can overcome worst case
hardness results.
  In this paper, we provide several results within this framework. For
center-based objectives, we present an algorithm that can optimally cluster
instances resilient to perturbations of factor $(1 + \sqrt{2})$, solving an
open problem of Awasthi et al.~\cite{ABS10}. For $k$-median, a center-based
objective of special interest, we additionally give algorithms for a more
relaxed assumption in which we allow the optimal solution to change in a small
$\epsilon$ fraction of the points after perturbation. We give the first bounds
known for $k$-median under this more realistic and more general assumption. We
also provide positive results for min-sum clustering which is typically a
harder objective than center-based objectives from approximability standpoint.
Our algorithms are based on new linkage criteria that may be of independent
interest.
  Additionally, we give sublinear-time algorithms, showing algorithms that can
return an implicit clustering from only access to a small random sample.
