[Theory] UC Theory Seminar: a reminder

[Alexander Razborov]

In 1.5 hours.

Euiwoong Lee, PhD
University of Michigan
 
 
 
 
Monday, February 12, 2024 at 3:30pm
Room – John Crerar Library 298
 
 
Title: Recent progresses on Correlation Clustering
 
Abstract: 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20240212/3014f5fd/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.jpg
Type: image/jpeg
Size: 68837 bytes
Desc: not available
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20240212/3014f5fd/attachment-0001.jpg>