2019/06/28 by Saba Ahmadi, Ahmadi, Saba, Sainyam Galhotra +7
Computer Science · Engineering · #Advanced Clustering Algorithms Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Packing Problems
paper · pdf · doi:10.48550/arxiv.1907.00117
openalex publication_date 2019/06/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 O(√log n⋅max\log(|E-|),log(k)\) approximation for general weighted graphs, where |E-| denotes the number of negative edges and k is the number of clusters in the optimum solution. 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 (i) O(r2)-approximation for min-max correlation clustering and min-max multicut for graphs that exclude Kr,r minors (ii) a 14-approximation for the min-max correlation clustering on complete graphs.