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

2 Scopus citations

Abstract

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
Pages13-26
Number of pages14
ISBN (Print)9783030179526
DOIs
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

Conference

Conference20th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2019
CountryUnited States
CityAnn Arbor
Period5/22/195/24/19

Keywords

  • Approximation algorithms
  • Correlation clustering
  • Multicut

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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

Cite this