Correlation Clustering

Year↕	Paper↕	Setting	Approx / Result↕	Technique	Notes
2006	Correlation Clustering in General Weighted Graphs Demaine et al.	Offline	O(log n)	—	Arbitrary edge weights; general (non-complete) graphs.
2008	Aggregating Inconsistent Information: Ranking and Clustering Ailon, Charikar, Newman	Offline Streaming	3	Pivot	The Pivot algorithm — the baseline for all subsequent work. Extends to insertion-only streams in random-order arrival.
2010	Online Correlation Clustering Mathieu et al.	Online Lower Bound	Ω(n) lower bound	—	No sublinear competitive ratio is achievable online: upon arrival, it is unknown whether an edge is part of a clique or a bridge between two cliques.
2015	Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphs Chawla, Makarychev, Schramm, Yaroslavtsev	Offline	2.06	LP Pivot	LP rounded via pivot-based approach. All edges have ±1 weights. Best known poly-time result for over a decade.
2021	Correlation Clustering in Constant Many Parallel Rounds Cohen-Addad et al.	Parallel / MPC	O(1)	—	Linear time; constant approximation in O(1) parallel rounds.
2021	Robust Online Correlation Clustering Lattanzi et al.	Online	Constant	Pivot	Semi-online model with O(1/ε) recourse per update. Studies robustness of Pivot under adversarial arrivals.
2021	Correlation Clustering in Data Streams Ahn, Cormode, Guha, McGregor, Wirth	Streaming	1 + ε	—	Dynamic, single-pass, semi-streaming (Õ(n) space). Exponential time. Near-optimal approximation ratio in streaming.
2022	Sublinear-Time Correlation Clustering via Random Sampling Assadi et al.	Offline	O(1)	—	Sublinear time via random sampling of vertex neighborhoods. Link TBD.
2022	Almost 3-Approximate Correlation Clustering in Constant Rounds Behnezhad, Charikar, Ma, Tan	Parallel / MPC	3 + ε	—	O(1/ε) parallel rounds; breaks the sequential Pivot bottleneck in the MPC model.
2022	Online and Consistent Correlation Clustering Cohen-Addad et al.	Online	Constant	—	Online with recourse; guarantees consistency between consecutive clusterings as the input evolves.
2023	Streaming Algorithms and Lower Bounds for Estimating Correlation Clustering Cost Assadi et al.	Streaming Lower Bound	cost estimation only	—	Uses polylog(n) bits of space to estimate the clustering cost — does not find the clustering itself. Includes matching lower bounds.
2023	Single-Pass Streaming Algorithms for Correlation Clustering Behnezhad et al.	Streaming	5	—	Single-pass streaming; 5-approximation.
2023	Single-Pass Pivot Algorithm for Correlation Clustering. Keep it Simple! Chakrabarty et al.	Streaming	3 + ε	Pivot	Insertion-only, single pass. Pivot-based; simple and practical.
2023	Handling Correlated Rounding Error via Preclustering: A 1.73-Approximation for Correlation Clustering Cohen-Addad et al.	Offline	1.73	LP	LP-based; O(n^{1/ε^O(1)}) time. Introduces preclustering to handle correlated rounding errors.
2023	Streaming Correlation Clustering with 1+ε Approximation Behnezhad et al.	Streaming	1 + ε	—	Dynamic, single-pass, semi-streaming; exponential runtime. Link TBD.
2024	A (3+ε)-Approximate Correlation Clustering Algorithm in Dynamic Streams Cambus, Dory, Goldenberg, Trabelsi	Streaming	3 + ε	—	Dynamic streams (insertions and deletions), single pass.
2024	Breaking 3-Factor Approximation for Correlation Clustering in Polylogarithmic Rounds Cao et al.	Parallel / MPC	2.4	LP	LP-based; runs in O(m^7.5) time. First result breaking the 3-approximation barrier in polylogarithmic parallel rounds.
2024	Understanding the Cluster Linear Program for Correlation Clustering Cao et al.	Offline	1.437	LP	LP-based rounding; integrality gap of 4/3. Significant advance in offline approximability.
2024	Combinatorial Correlation Clustering Cohen-Addad et al.	Offline	2 − 2/13 + ε	—	Local-search based; no LP required. Breaks the 2-approximation barrier combinatorially.
2024	Combinatorial Correlation Clustering (Streaming) Cohen-Addad et al.	Streaming	1.847	—	Insertion-only streams. Best known approximation for streaming CC to date.
2025	Learning-Augmented Streaming Algorithms for Correlation Clustering Dong et al.	Streaming Learning-Aug.	min{2.06β, 3} + ε	LP Pivot	Two variants: insertion-only and dynamic, both single-pass. Uses ML-predicted pairwise distances (β = prediction quality). Achieves better-than-3 with good predictions; degrades gracefully to Pivot otherwise. ICLR 2025.

No papers match the current filter or search.

Correlation Clustering — Paper Index