Abstract :
What are the performance guarantees of the algorithms used in practice
for clustering problems?
In a paper with Phil Klein and Claire Mathieu, we give the
first polynomial-time approximation schemes for the following problems:
(1) uniform facility location in edge-weighted planar graphs;
(2) $k$-median and $k$-means in edge-weighted planar graphs;
(3) $k$-means in Euclidean space of bounded dimension.
The algorithm is a standard, widely-used local search heuristic where
the local neighborhood of a solution $S$ consists of all solutions
obtained from $S$ by removing and adding $1/\eps^{O(1)}$ centers.
In a second line of work with Chris Schwiegelshohn, we show that this
algorithm also performs near-optimaly for several types of instances
that aim at characterizing the structure of real-world instances
stemming from machine learning and data analysis.
Those results make a step toward understanding the success of local
search heuristics in practice.
When: Friday Nov, 25th 2016
Where: Amphi B – ENS de Lyon — Site Monod
