Correlation Clustering and Biclustering With Locally Bounded Errors

DOI10.1109/TIT.2018.2819696MaRDI QIDQ5375565zbMATH OpenOpenAlexWikidataFDO

Authors Gregory J. Puleo, Olgica Milenkovic

Publication date 14 September 2018

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1506.08189

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Graph theory (including graph drawing) in computer science (68R10) Applications of mathematical programming (90C90) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

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 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.

Cited in

(10)

• Approximation algorithm for the balanced 2-correlation clustering problem on well-proportional graphs
• Approximation algorithm for min-max correlation clustering problem with outliers
• Approximation algorithms for two variants of correlation clustering problem
• _p-norm multiway cut
• Complexity of modification problems for reciprocal best match graphs
• Metric-Constrained Optimization for Graph Clustering Algorithms
• Approximation Algorithms for the Capacitated Min–Max Correlation Clustering Problem
• Approximation algorithm for min-max correlation clustering problem with penalties
• Min-Max correlation clustering via neighborhood similarity
• Fair correlation clustering with global and local guarantees

This page was built for publication: Correlation Clustering and Biclustering With Locally Bounded Errors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5375565)