Near Optimal LP Rounding Algorithm for Correlation Clustering on   Complete and Complete k-partite Graphs
  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 - \varepsilon$ for a fixed constant $\varepsilon$, 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). 
Shuchi Chawla, Konstantin Makarychev, Tselil Schramm, Grigory   Yaroslavtsev
cs.DS