TY - GEN

T1 - Near optimal LP rounding algorithm for correlation clustering on complete and complete k-partite graphs

AU - Chawla, Shuchi

AU - Makarychev, Konstantin

AU - Schramm, Tselil

AU - Yaroslavtsev, Grigory

N1 - Publisher Copyright:
© Copyright 2015 ACM.
Copyright:
Copyright 2016 Elsevier B.V., All rights reserved.

PY - 2015/6/14

Y1 - 2015/6/14

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

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

UR - http://www.scopus.com/inward/record.url?scp=84958778713&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84958778713&partnerID=8YFLogxK

U2 - 10.1145/2746539.2746604

DO - 10.1145/2746539.2746604

M3 - Conference contribution

AN - SCOPUS:84958778713

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 219

EP - 228

BT - STOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing

PB - Association for Computing Machinery

T2 - 47th Annual ACM Symposium on Theory of Computing, STOC 2015

Y2 - 14 June 2015 through 17 June 2015

ER -