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

Abstract:

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

• For complete graphs our appoximation is 2.06−ε for a fixed constant ε, which almost matches the previously known integrality gap of 2.
• For complete k-partite graphs our approximation is 3. We also show a matching integrality gap.
• For complete graphs with edge weights satisfying triangle inequalities and probability constraints, our approximation is 1.5, and we show an integrality gap of 1.2.

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/