We give new rounding schemes for the standard linear programming relaxationof the correlation clustering problem, achieving approximation factors almostmatching the integrality gaps: - For complete graphs our appoximation is $2.06 - \varepsilon$ for a fixedconstant $\varepsilon$, which almost matches the previously known integralitygap of $2$. - For complete $k$-partite graphs our approximation is $3$. We also show amatching integrality gap. - For complete graphs with edge weights satisfying triangle inequalities andprobability constraints, our approximation is $1.5$, and we show an integralitygap of $1.2$. Our results improve a long line of work on approximation algorithms forcorrelation clustering in complete graphs, previously culminating in a ratio of$2.5$ for the complete case by Ailon, Charikar and Newman (JACM'08). In theweighted complete case satisfying triangle inequalities and probabilityconstraints, the same authors give a $2$-approximation; for the bipartite case,Ailon, Avigdor-Elgrabli, Liberty and van Zuylen give a $4$-approximation(SICOMP'12).
展开▼
