Title: On the Local Structure of Stable Clustering Instances

Abstract:
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.

Bio:
Chris Schwiegelshohn is currently a post-doc in Sapienza, University
of Rome. He did his Phd in Dortmund with a thesis on "Algorithms for
Large-Scale Graph and Clustering Problems". Chris' research interests
include streaming and approximation algorithms as well as machine
learning.

Date: 8th of February 2018, 12:00-13:00

Location: Manno, Galleria 1, 2nd floor, room G1-204

Registration: Pizza and drinks will be offered at the end of the talk.
If you plan to attend, please register in a timely fashion at the
following link so that we will have no shortage of food:
https://doodle.com/poll/sp294b469e9x44bf