Eventi DIAG

Chris Schwiegelsohohn: On the Local Structure of Stable Clustering Instances - Chris Schwiegelshohn, DIAG, Sapienza University of Rome
2017-10-12 14:00 (Europe/Paris) | Aula Magna DIAG, via Ariosto 25, I floow
As an optimization problem, clustering exhibits a strikingphenomenon: It is generally regarded as easy in practice, while theoryclassifies it among the computationally intractable problems. To addressthis dichotomy, research has identified a number of conditions a data setmust satisfy for a clustering to be (1) easily computable and (2)meaningful.In this talk we show that all previously proposed notions of struturednessof a data set are fundamentally local properties, i.e. the global optimumis in well defined sense close to a local optimum. As a corollary, thisimplies that the Local Search heuristic has strong performance guaranteesfor both the tasks of recovering the underlying optimal clustering andobtaining a clustering of small cost.Joint work with Vincent Cohen-Addad
