## Abstract

We consider a generalized version of the correlation clustering problem, defined as follows. Given a complete graph G whose edges are labeled with + or -, we wish to partition the graph into clusters while trying to avoid errors: + edges between clusters or - edges within clusters. Classically, one seeks to minimize the total number of such errors. We introduce a new framework that allows the objective to be a more general function of the number of errors at each vertex (for example, we may wish to minimize the number of errors at the worst vertex) and provides a rounding algorithm which converts 'fractional clusterings' into discrete clusterings while causing only a constant-factor blowup in the number of errors at each vertex. This rounding algorithm yields constant-factor approximation algorithms for the discrete problem under a wide variety of objective functions.

Original language | English (US) |
---|---|

Pages (from-to) | 4105-4119 |

Number of pages | 15 |

Journal | IEEE Transactions on Information Theory |

Volume | 64 |

Issue number | 6 |

DOIs | |

State | Published - Jun 2018 |

## Keywords

- Clustering methods
- approximation algorithms

## ASJC Scopus subject areas

- Information Systems
- Computer Science Applications
- Library and Information Sciences