### 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 language | English (US) |
---|---|

Title of host publication | STOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing |

Publisher | Association for Computing Machinery |

Pages | 219-228 |

Number of pages | 10 |

ISBN (Electronic) | 9781450335362 |

DOIs | |

State | Published - Jun 14 2015 |

Event | 47th Annual ACM Symposium on Theory of Computing, STOC 2015 - Portland, United States Duration: Jun 14 2015 → Jun 17 2015 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

Volume | 14-17-June-2015 |

ISSN (Print) | 0737-8017 |

### Other

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

Country | United States |

City | Portland |

Period | 6/14/15 → 6/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

*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