Clustering under Perturbation Resilience

Recently, Bilu and Linial [10] formalized an implicit assumption often made when choosing a clus-tering objective: that the optimum clustering to the objective should be preserved under small multiplica-tive perturbations to distances between points. They showed that for max-cut clustering it is possible to circumvent NP-hardness and obtain polynomial-time algorithms for instances resilient to large (factor O( n)) perturbations, and subsequently Awasthi et al. [3] considered center-based objectives, giving algorithms for instances resilient to O(1) factor perturbations. In this paper, we greatly advance this line of work. For center-based objectives, we present an algorithm that can optimally cluster instances resilient to (1 + 2)-factor perturbations, solving an open problem of Awasthi et al.[3]. 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 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 a generally much harder objective than center-based objectives. 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 clus-tering from only access to a small random sample.