Correlation Clustering and Biclustering with Locally Bounded Errors

Gregory J. Puleo, Olgica Milenkovic

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)4105-4119
Number of pages15
JournalIEEE Transactions on Information Theory
Volume64
Issue number6
DOIs
StatePublished - Jun 2018

Keywords

  • Clustering methods
  • approximation algorithms

ASJC Scopus subject areas

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

Fingerprint

Dive into the research topics of 'Correlation Clustering and Biclustering with Locally Bounded Errors'. Together they form a unique fingerprint.

Cite this