报告题目： Handling Correlated Rounding Error via Preclustering: A 1.73-approximation for Correlation Clustering
报告时间：8月14日（周一）下午16:30
报告地点： 信息楼535
报告简介：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 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 Cohen-Addad et al. 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. This is based on joint work with Cohen-Addad, Lee and Newman. The paper will appear in FOCS 2023.
报告人简介：
栗师，南京大学教授、博士生导师。本科毕业于清华大学计算机科学与技术系，以及第一届姚期智理论计算机科学实验班。于普林斯顿大学获得博士学位，之后在芝加哥丰田技术研究院担任助理研究教授，纽约州立大学布法罗分校担任助理教授，并于2020年在该校获得副教授职称。2023年初入职南京大学。栗师教授的研究方向为理论计算机科学领域与算法设计。他在若干经典和基础问题上做出重大突破，解决了很多十多年未能解决的公开难题。其多个结果分别获得获得理论计算机科学一流会议ICALP 2011获单独作者最优秀学生论文奖、领域顶级会议FOCS 2012最优秀论文奖和发表于计算机科学领域的旗舰期刊 Journal of the ACM (JACM)上。多项结果发表在理论计算机科学最高期刊SIAM Journal on Computing (SICOMP) 上，以及ACM Transactions on Algorithms (TALG)，Information and Computation(I&C)等国际一流期刊上。他在FOCS, STOC和SODA三大领域顶级会议上发表文章30余篇。
