Theory Seminar

Recent progresses on Correlation Clustering

Euiwoong LeeUniversity of Michigan
WHERE:
3725 Beyster BuildingMap
WHEN:
Friday, March 8, 2024 @ 2:00 pm - 3:00 pm
This event is free and open to the publicAdd to Google Calendar
SHARE:
Correlation Clustering is one of the most well-studied graph clustering problems. The input is a complete graph where each edge is labeled either “+” or “-“, and the goal is to partition the vertex set into (an arbitrary number of) clusters to minimize (the number of + edges between different clusters) + (the number of – edges within the same cluster). Until recently, the best polynomial-time approximation ratio was 2.06, nearly matching the integrality gap of 2 for the standard LP relaxation.

Since 2022, we have bypassed this barrier and progressively improved the approximation ratio, with the current ratio being 1.44. Based on a new relaxation inspired by the Sherali-Adams hierarchy, the algorithm introduces and combines several tools considered in different contexts, including “local to global correlation rounding” and “combinatorial preclusering”. In this talk, I will describe the current algorithm as well as how it has been inspired by various viewpoints.

Joint work with Nairen Cao, Vincent Cohen-Addad, Shi Li, Alantha Newman, and Lukas Vogl

Organizer

Greg Bodwin

Organizer

Euiwoong Lee