Seminar Details
Handling Correlated Rounding Error via Preclustering: A 1.73-approximation for Correlation Clustering
- Start Date: November 15, 2023
- Event Start Time: 11:00 AM
- Event End Time: 12:00 PM
- Seminar Series: Theoretical Computer Science Seminar
- Presenter(s): Vincent Cohen-Addad - Google
- Event Location: Conference Room 301 | Rutgers University | CoRE Building | 96 Frelinghuysen Road
- Event Additional Info: <p>See: <a href="https://theory.cs.rutgers.edu/theory_seminar">https://theory.cs.rutgers.edu/theory_seminar</a></p>
- Presentation Type: Stand Alone Presentation
- Abstract:
We consider the classic Correlation Clustering problem: Given a complete graph where edges are labelled either + or −, the goal is to find a partition of the vertices that minimizes the number of the +edges across parts plus the number of the −edges within parts. Recently, Cohen-Addad, Lee and Newman [CLN22] presented a 1.994-approximation algorithm for the problem using the Sherali-Adams hierarchy, hence breaking through the integrality gap of 2 for the classic linear program and improving upon the 2.06-approximation of Chawla, Makarychev, Schramm and Yaroslavtsev [CMSY15].
We significantly improve the state-of-the-art by providing a 1.73-approximation for the problem. Our approach introduces a preclustering of Correlation Clustering instances that allows us to essentially ignore the error arising from the correlated rounding used by [CLN22]. This additional power simplifies the previous algorithm and analysis. More importantly, it enables a new set-based rounding that complements the previous roundings. A combination of these two rounding algorithms yields the improved bound.
Joint work with Euiwoong Lee, Shi Li, Alantha Newman To appear FOCS'23.