Abstract
In the talk, I will describe the Correlation Clustering problem and give an overview of known results. I will present a new 2.06 approximation algorithm for the problem on complete graphs. Then, I will describe a semi-random model for the Correlation Clustering problem with noisy partial information, and give PTAS for semi-random instances.
Based on joint works with Shuchi Chawla, Tselil Schramm, and Grigory Yaroslavtsev; and with Yury Makarychev and Aravindan Vijayaraghavan.