Journal
STOC'15: PROCEEDINGS OF THE 2015 ACM SYMPOSIUM ON THEORY OF COMPUTING
Volume -, Issue -, Pages 219-228Publisher
ASSOC COMPUTING MACHINERY
DOI: 10.1145/2746539.2746604
Keywords
-
Categories
Funding
- NSF [CCF-1320854]
- NSF Graduate Research Fellowship [DGE 1106400]
- ICERM Institute Postdoctoral Fellowship at Brown
- Warren Center Postdoctoral Fellowship at Penn
Ask authors/readers for more resources
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 - epsilon, 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).
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available