Research map / Learning theory and algorithms / Clustering
Towards Better-than-2 Approximation for Constrained Correlation Clustering
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.
Shows that, conditional on efficiently solving the exponentially large Constrained Cluster LP, combining LP-guided local search with penalized local search and LP-based sampling/pivoting yields a (1.92+ε)-approximation for Constrained Correlation Clustering.
Problem
Constrained Correlation Clustering (with must-link and cannot-link hard constraints) has the best known approximation factor of 3, and the goal is a better-than-2 approximation.
Approach
Uses a fractional optimal Constrained Cluster LP solution to guide local search directly (embedding hard constraints in the LP support), adds a penalized second local search to force a different clustering, and mixes the two local-search outputs with an LP-sampled clustering via pivoting so that a better-than-2 solution is guaranteed.
Key results
- Under the assumption that the Constrained Cluster LP can be solved efficiently, the algorithm achieves a (1.92+ε)-approximation for Constrained Correlation Clustering, improving on the prior factor of 3.
- Local search output L is shown to be 2-approximate, and is better than 2-approximate unless specific conditions on LP cost hold.
- The pivoting procedure P is shown to be (24+3ε)δ-approximate with δ=2/25 when neither local search solution is (2-δ)-approximate.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a Constrained Cluster LP solution to guide local search, conditional on efficiently solving the LP | Constrained Correlation Clustering · Constrained Correlation Clustering | approximation factor: 3 -> (1.92 + ε) | Helped |
Surprising findings
- The peer-reviewed version claimed an efficient LP solver, but an error was found after review, so the results are conditional on the existence of a valid LP solution.
Limitations
- Result is conditional on an efficient algorithm for solving the Constrained Cluster LP, which is not provided.
- Approximation factor 1.92 is only an improvement over 2 by a small margin and is theoretical, with no experiments.
- Inapproximability for the constrained setting beyond those for standard correlation clustering is unknown.
Experimental setup
Metrics: approximation ratio
Baselines: van Zuylen and Williamson 3-approximation Cohen-Addad et al. 2024 local search 2+epsilon Cao et al. 2024 1.437-approximation
Builds on: Cluster LP (Cao et al. 2024) local search for correlation clustering (Cohen-Addad et al. 2024) van Zuylen and Williamson 3-approximation
Closest papers by meaning
- Instance-Specific Approximation Ratios for Correlation Clustering and Max-Cut (ICML 2026 · similarity 0.90)
- Efficient Testing for Correlation Clustering: Improved Algorithms and Optimal Bounds (ICLR 2026 · similarity 0.90)
- Improved Approximation Algorithms for Chromatic and Pseudometric-Weighted Correlation Clustering (NeurIPS 2025 · similarity 0.88)
- Correlation Clustering Beyond the Pivot Algorithm (ICML 2025 · similarity 0.87)
- Efficient Constrained K-center Clustering with Background Knowledge (AAAI 2024 · similarity 0.87)
- Sparse-pivot: Dynamic correlation clustering for node insertions (ICML 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.