主讲人
Nairen Cao NYU Tandon School of Engineering 时间 2026年4月7日 星期二 上午 10:00-11:00 地点 腾讯会议https://work.weixin.qq.com/webapp/tm/JMeJOxMg07d
Abstract Correlation Clustering is a central problem in graph clustering: given a complete graph with edges labeled + or −, the goal is to partition the vertices into clusters that minimize disagreements: + edges that lie across different clusters together with − edges that lie within the same cluster. In this talk, I will present a simple yet powerful new framework for the problem based on a strong linear programming relaxation, which we call the Clustering LP. We show that this LP leads to a simple rounding algorithm achieving a 1.437-approximation, improving on previous results. This is joint work with Vincent Cohen-Addad, Shi Li, Euiwoong Lee, David Rasmussen Lolck, Alantha Newman, Mikkel Thorup, Lukas Vogl, Shuyi Yan, and Hanwen Zhang. Biography Nairen Cao is a Faculty Fellow at NYU Tandon School of Engineering working in theoretical computer science. His research lies in algorithm design and analysis, with a particular focus on parallel and distributed algorithms for graph problems and combinatorial optimization. He has worked on topics including shortest paths, correlation clustering, and related problems in modern parallel models. His papers have appeared in venues such as STOC, SODA, SPAA, PODC, ESA, and ICALP, and his work received Outstanding Paper Awards at SPAA in 2022 and 2023. He earned his PhD in Computer Science from Georgetown University in 2022.
