Chris Schwiegelsohohn: On the Local Structure of Stable Clustering Instances

Data dell'evento: 
Giovedì, 12 Ottobre, 2017 - 14:00
Aula Magna DIAG, via Ariosto 25, I floow
Chris Schwiegelshohn, DIAG, Sapienza University of Rome

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)

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