Research map / Learning theory and algorithms / Clustering

Improved Approximation Algorithms for Chromatic and Pseudometric-Weighted Correlation Clustering

NeurIPS 2025 · Learning theory and algorithms › Clustering · approach: Correlation clustering · 1 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Improves LP-based pivot approximation for chromatic correlation clustering (2.5 to 2.15) with new neutral-edge rounding, and gives a tight 10/3 LP-pivot approximation for pseudometric-weighted correlation clustering.

Problem

Approximation algorithms for Chromatic Correlation Clustering (multi-colored edge labels) and pseudometric-weighted Correlation Clustering (edge weights satisfying the triangle inequality).

Approach

LP-based pivoting with problem-specific rounding functions, analyzed via triple-based charging; for CCC a new piecewise rounding function for neutral edges, and for weighted CC a piecewise-linear rounding function reaching 10/3, with matching lower bounds within the framework.

Key results

• Pseudometric-weighted CC: LP-Pivot with a piecewise-linear rounding function gives a 10/3-approximation, and no rounding function in the framework gives a lower factor.
• Chromatic CC: LP-CCC with the new neutral-edge rounding f° achieves a 2.15-approximation, improving on the prior 2.5.
• Lower bound of 2.11 for LP-CCC within the same triple-based framework.

Measured effects reported in the paper

Limitations

• Lower bounds hold only within the LP-pivot framework with the given LP relaxation and rounding functions
• The rounding function for CCC is intricate and was computed numerically to avoid violated regions
• The proofs rely on extensive case analysis

Experimental setup

Metrics: approximation ratio (expected cost vs LP)

Baselines: Xiu et al. 2.5-approximation LP-CCC Anava et al. 4-approximation Charikar and Gao LP-UMVD-Pivot

Builds on: LP-Pivot Chawla et al. 2.06 rounding Xiu et al. LP-CCC UMVD pivot (Charikar and Gao)

Closest papers by meaning

• Chromatic Correlation Clustering, Revisited (NeurIPS 2022 · similarity 0.94)
• Correlation Clustering via Strong Triadic Closure Labeling: Fast Approximation Algorithms and Practical Lower Bounds (ICML 2022 · similarity 0.90)
• Towards Better-than-2 Approximation for Constrained Correlation Clustering (ICML 2025 · similarity 0.88)
• Improved Algorithms for Overlapping and Robust Clustering of Edge-Colored Hypergraphs: An LP-Based Combinatorial Approach (NeurIPS 2025 · similarity 0.88)
• Correlation Clustering Beyond the Pivot Algorithm (ICML 2025 · similarity 0.87)
• Learning-Augmented Streaming Algorithms for Correlation Clustering (NeurIPS 2025 · similarity 0.87)