A 4-approximation algorithm for min max correlation clustering

2023/10/13 by Holger Heidrich, Heidrich, Holger, Jannik Irmai +3 · 2 citations
Computer Science · Decision Sciences · #Advanced Clustering Algorithms Research #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Multi-Criteria Decision Making

paper · pdf · doi:10.48550/arxiv.2310.09196

openalex publication_date 2023/10/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We introduce a lower bounding technique for the min max correlation clustering problem and, based on this technique, a combinatorial 4-approximation algorithm for complete graphs. This improves upon the previous best known approximation guarantees of 5, using a linear program formulation (Kalhan et al., 2019), and 40, for a combinatorial algorithm (Davies et al., 2023a). We extend this algorithm by a greedy joining heuristic and show empirically that it improves the state of the art in solution quality and runtime on several benchmark datasets.

Cited by

• Online Correlation Clustering: Simultaneously Optimizing All ℓ_p-norms
• Learning-Augmented Streaming Algorithms for Correlation Clustering

Related

• Fast Combinatorial Algorithms for Min Max Correlation Clustering
• Min-Max Correlation Clustering via Neighborhood Similarity
• Improved Combinatorial Approximations for Weighted Correlation Clustering
• A Simple and Fast (3+ε)-approximation for Constrained Correlation Clustering
• Understanding the Cluster LP for Correlation Clustering