### 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: -I-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 provide 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) |
---|---|

Title of host publication | 33rd International Conference on Machine Learning, ICML 2016 |

Editors | Maria Florina Balcan, Kilian Q. Weinberger |

Publisher | International Machine Learning Society (IMLS) |

Pages | 1380-1388 |

Number of pages | 9 |

ISBN (Electronic) | 9781510829008 |

State | Published - Jan 1 2016 |

Event | 33rd International Conference on Machine Learning, ICML 2016 - New York City, United States Duration: Jun 19 2016 → Jun 24 2016 |

### Publication series

Name | 33rd International Conference on Machine Learning, ICML 2016 |
---|---|

Volume | 2 |

### Other

Other | 33rd International Conference on Machine Learning, ICML 2016 |
---|---|

Country | United States |

City | New York City |

Period | 6/19/16 → 6/24/16 |

### ASJC Scopus subject areas

- Artificial Intelligence
- Software
- Computer Networks and Communications

## Fingerprint Dive into the research topics of 'Correlation clustering and biclustering with locally bounded errors'. Together they form a unique fingerprint.

## Cite this

*33rd International Conference on Machine Learning, ICML 2016*(pp. 1380-1388). (33rd International Conference on Machine Learning, ICML 2016; Vol. 2). International Machine Learning Society (IMLS).