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

Shuchi Chawla, Konstantin Makarychev, Tselil Schramm, Grigory Yaroslavtsev

Research output: Chapter in Book/Report/Conference proceedingConference contribution

25 Scopus citations

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

Original languageEnglish (US)
Title of host publicationSTOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing
PublisherAssociation for Computing Machinery
Pages219-228
Number of pages10
ISBN (Electronic)9781450335362
DOIs
StatePublished - Jun 14 2015
Event47th Annual ACM Symposium on Theory of Computing, STOC 2015 - Portland, United States
Duration: Jun 14 2015Jun 17 2015

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
Volume14-17-June-2015
ISSN (Print)0737-8017

Other

Other47th Annual ACM Symposium on Theory of Computing, STOC 2015
CountryUnited States
CityPortland
Period6/14/156/17/15

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Near optimal LP rounding algorithm for correlation clustering on complete and complete k-partite graphs'. Together they form a unique fingerprint.

  • Cite this

    Chawla, S., Makarychev, K., Schramm, T., & Yaroslavtsev, G. (2015). Near optimal LP rounding algorithm for correlation clustering on complete and complete k-partite graphs. In STOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing (pp. 219-228). (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. 14-17-June-2015). Association for Computing Machinery. https://doi.org/10.1145/2746539.2746604