Center-based clustering under perturbation stability

Pranjal Awasthi, Avrim Blum, Or Sheffet

Research output: Contribution to journalArticlepeer-review

50 Scopus citations

Abstract

Clustering under most popular objective functions is NP-hard, even to approximate well, and so unlikely to be efficiently solvable in the worst case. Recently, Bilu and Linial (2010) [11] suggested an approach aimed at bypassing this computational barrier by using properties of instances one might hope to hold in practice. In particular, they argue that instances in practice should be stable to small perturbations in the metric space and give an efficient algorithm for clustering instances of the Max-Cut problem that are stable to perturbations of size O(n1/2). In addition, they conjecture that instances stable to as little as O(1) perturbations should be solvable in polynomial time. In this paper we prove that this conjecture is true for any center-based clustering objective (such as k-median, k-means, and k-center). Specifically, we show we can efficiently find the optimal clustering assuming only stability to factor-3 perturbations of the underlying metric in spaces without Steiner points, and stability to factor 2+3 perturbations for general metrics. In particular, we show for such instances that the popular Single-Linkage algorithm combined with dynamic programming will find the optimal clustering. We also present NP-hardness results under a weaker but related condition.

Original languageEnglish (US)
Pages (from-to)49-54
Number of pages6
JournalInformation Processing Letters
Volume112
Issue number1-2
DOIs
StatePublished - Jan 15 2012

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Keywords

  • Analysis of algorithms
  • Clustering
  • Stability conditions
  • k-Means
  • k-Median

Fingerprint Dive into the research topics of 'Center-based clustering under perturbation stability'. Together they form a unique fingerprint.

Cite this