Chris Schwiegelsohohn: On the Local Structure of Stable Clustering Instances
As an optimization problem, clustering exhibits a striking
phenomenon: It is generally regarded as easy in practice, while theory
classifies it among the computationally intractable problems. To address
this dichotomy, research has identified a number of conditions a data set
must satisfy for a clustering to be (1) easily computable and (2)
meaningful.
In this talk we show that all previously proposed notions of struturedness
of a data set are fundamentally local properties, i.e. the global optimum
is in well defined sense close to a local optimum. As a corollary, this
implies that the Local Search heuristic has strong performance guarantees
for both the tasks of recovering the underlying optimal clustering and
obtaining a clustering of small cost.
Joint work with Vincent Cohen-Addad