Min-Max Correlation Clustering via MultiCut

Saba Ahmadi*, Samir Khuller, Barna Saha

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

16 Scopus citations


Correlation clustering is a fundamental combinatorial optimization problem arising in many contexts and applications that has been the subject of dozens of papers in the literature. In this problem we are given a general weighted graph where each edge is labeled positive or negative. The goal is to obtain a partitioning (clustering) of the vertices that minimizes disagreements – weight of negative edges trapped inside a cluster plus positive edges between different clusters. Most of the papers on this topic mainly focus on minimizing total disagreement, a global objective for this problem. In this paper we study a cluster-wise objective function that asks to minimize the maximum number of disagreements of each cluster, which we call min-max correlation clustering. The min-max objective is a natural objective that respects the quality of every cluster. In this paper, we provide the first nontrivial approximation algorithm for this problem achieving an approximation for general weighted graphs. To do so, we also obtain a corresponding result for multicut where we wish to find a multicut solution while trying to minimize the total weight of cut edges on every component. The results are then further improved to obtain an approximation for min-max correlation clustering and min-max multicut for graphs that exclude minors.

Original languageEnglish (US)
Title of host publicationInteger Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Proceedings
EditorsAndrea Lodi, Viswanath Nagarajan
PublisherSpringer Verlag
Number of pages14
ISBN (Print)9783030179526
StatePublished - 2019
Event20th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2019 - Ann Arbor, United States
Duration: May 22 2019May 24 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11480 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference20th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2019
Country/TerritoryUnited States
CityAnn Arbor


  • Approximation algorithms
  • Correlation clustering
  • Multicut

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Min-Max Correlation Clustering via MultiCut'. Together they form a unique fingerprint.

Cite this