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