Research map / Learning theory and algorithms / Clustering

Atoms and Pivot Based Correlation Clustering

NeurIPS 2026 · Learning theory and algorithms › Clustering · approach: Correlation clustering

Read the paperCheck your idea against 108,967 papers

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

Studies pivot-based correlation clustering and proposes an atom-based refinement of the classic factor-3 pivot algorithm, based only on the abstract's framing of worst-case instances.

Problem

Correlation clustering minimizes disagreements (cross-cluster edges and within-cluster non-edges); the classic pivot algorithm of Ailon, Charikar and Chawla achieves factor 3, but worst-case instances are highly structured.

Approach

Abstract only indicates the paper builds on pivot-based correlation clustering and the notion of "atoms" to address the factor-3 worst case; the precise mechanism is not stated in the provided text.

Limitations

• Full text unavailable; only the abstract was available

Experimental setup

Baselines: pivot-based correlation clustering

Builds on: Ailon-Charikar-Chawla pivot algorithm

Closest papers by meaning

• Correlation Clustering Beyond the Pivot Algorithm (ICML 2025 · similarity 0.92)
• Sparse-pivot: Dynamic correlation clustering for node insertions (ICML 2025 · similarity 0.90)
• Improved Approximation Algorithms for Chromatic and Pseudometric-Weighted Correlation Clustering (NeurIPS 2025 · similarity 0.88)
• Towards Better-than-2 Approximation for Constrained Correlation Clustering (ICML 2025 · similarity 0.88)
• Online Sparsification of Bipartite-Like Clusters in Graphs (ICML 2025 · similarity 0.87)
• Dynamic Correlation Clustering in Sublinear Update Time (ICML 2024 · similarity 0.87)