Speaker: Shi Li Nanjing University
Time: 2023-12-06 14:30-2023-12-06 16:00
Venue:

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 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. 

We present several techniques that improve the state-of-the-art approximation ratio. We propose the cluster LP as a strong linear program that might tightly capture the approximability of Correlation Clustering. It unifies all the previous relaxations for the problem. It is exponential-sized, but we show that it can be (1 + ε)-approximately solved in polynomial time for any ε > 0, using a preclustering technique we introduced. It allows us to essentially ignore the error arising from the correlated rounding used by Cohen-Addad et al. 

We demonstrate the power of the cluster LP by presenting a simple rounding algorithm, and providing two analyses, one analytically proving a 1.49-approximation and the other solving a factor-revealing SDP to show a 1.437-approximation. 

This is based on joint work with Cohen-Addad, Lee and Newman, in FOCS 2023, and an ongoing work with Cao, Cohen-Addad, Lee, Newman and Vogl.

Short Bio:

Shi Li is a professor at Nanjing University. He graduated from the Department of Computer Science and Technology of Tsinghua University with a bachelor's degree and the first Yao Qizhi Theory Computer Science Experimental Class. He received his PhD from Princeton University and then served as an assistant research Professor at the Toyota Institute of Technology in Chicago and an assistant professor at the State University of New York at Buffalo, where he received an associate professor title in 2020. He joined Nanjing University in 2023. His research interests include theoretical computer science and algorithm design. He made major breakthroughs in several classic and fundamental problems and solved many public problems that had not been solved for more than a decade. He has published more than 30 papers at FOCS, STOC and SODA, the top three conferences in the field.