Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs
Shuchi Chawla, Konstantin Makarychev, Tselil Schramm, Grigory Yaroslavtsev · 2015
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 approximation is 2.06 - ε, 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.