Name
Title | ||
|---|---|---|
Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphs. |
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 - \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). |
Year | Venue | DocType |
|---|---|---|
2014 | CoRR | Journal |
Volume | Citations | PageRank |
abs/1412.0681 | 0 | 0.34 |
References | Authors | |
0 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shuchi Chawla | 1 | 1872 | 186.94 |
| Konstantin Makarychev | 2 | 0 | 1.01 |
| Tselil Schramm | 3 | 0 | 1.69 |
| Grigory Yaroslavtsev | 4 | 209 | 17.36 |