Seminars

View all Seminars  |  Download ICal for this event

Correlated Rounding for Correlation Clustering

Series: Bangalore Theory Seminars

Speaker: Alantha Newman G-SCOP Laboratory in Grenoble France

Date/Time: Sep 16 11:00:00

Location: Microsoft Teams - ON-LINE

Abstract:
Given a complete graph G = (V, E) where each edge is labeled + or -, the correlation clustering problem asks to partition V into clusters to minimize the number of +edges between different clusters plus the number of -edges within the same cluster. The approximability of correlation clustering has been actively investigated [BBC04, CGW05, ACN08], culminating in a 2.06-approximation algorithm [CMSY15], based on rounding the standard LP relaxation. Since the integrality gap for this formulation is 2, it has remained a major open question to determine if the approximation factor of 2 can be reached, or even breached. In this talk, we show how to achieve a factor of 2+eps based on O(1/eps^2) rounds of the Sherali-Adams hierarchy. To round this relaxation, we adapt the correlated rounding originally developed for CSPs [BRS11, GS11, RT12]. To go below this approximation ratio, we go beyond the traditional triangle-based analysis by employing a global charging scheme that amortizes the total cost of the rounding across different triangles.

Joint work with Vincent Cohen-Addad and Euiwoong Lee.

For more details please visit: Link

Microsoft teams link:

Link


Hosts: Rahul Madhavan and Rameesh Paul