DIMACS Theoretical Computer Science Seminar

Title: Near Optimal LP Rounding for Correlation Clustering on Complete Graphs

Speaker: Grigory Yaroslavtsev, U Penn

Date: Wednesday, January 28, 2015 11:00am-12:00pm

Location: CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ


We give new rounding schemes for the standard linear programming relaxation of the correlation clustering problem, achieving approximation factors almost matching the integrality gaps:

Our results improve a long line of work on approximation algorithms for correlation clustering in complete graphs, previously culminating in a ratio of 2.5 for the complete case by Ailon, Charikar and Newman (JACM'08). In the weighted complete case satisfying triangle inequalities and probability constraints, the same authors give a 2-approximation; for the bipartite case, Ailon, Avigdor-Elgrabli, Liberty and van Zuylen give a 4-approximation (SICOMP'12).

Joint work with Shuchi Chawla, Konstantin Makarychev and Tselil Schramm.

See: http://www.math.rutgers.edu/~sk1233/theory-seminar/S15/