  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).
