Correlation Clustering Beyond the Pivot Algorithm
Soheil Behnezhad, Moses Charikar, Vincent Cohen-Addad, Alma Ghafari, Weiyun Ma
2025Year
2Top-tier citations
Abstract
We study the classic correlation clustering problem. Given n objects and a complete labeling of the object-pairs as either "similar" or "dissimilar", the goal is to partition the objects into arbitrarily many clusters while minimizing disagreements with the labels.
Ask about this paper
Your agent reads all of it.
Lune indexed this paper to the last equation, along with the top-tier papers that cite it. Ask a question and the answer quotes them.
Your agent calls
Luneget_paper_fulltext
Free to start. No credit card required.
Terminal
Install the CLIlune papers fulltext 6f45f643-aa21-40a9-a5e7-08c3b991a498Cited by top-tier papers2
- Learning-Augmented Streaming Algorithms for Correlation ClusteringYinhao Dong, Shan Jiang, Shi Li, Pan PengNeurIPS 2025 · 1 citation
- Estimating Correlation Clustering Cost in Node-Arrival StreamKaiwen Liu, Seba Daniela Villalobos, Qin ZhangICML 2026
Builds on9
- Correlation Clustering in Constant Many Parallel RoundsVincent Cohen-Addad, Silvio Lattanzi, Slobodan Mitrovic, Ashkan Norouzi-Fard et al.ICML 2021 · 51 citations
- Scalable Community Detection via Parallel Correlation ClusteringJessica Shi, Laxman Dhulipala, David Eisenstat, Jakub Lacki et al.VLDB 2021 · 41 citations
- Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple!Konstantin Makarychev, Sayak ChakrabartyNeurIPS 2023 · 33 citations
- Correlation Clustering via Strong Triadic Closure Labeling: Fast Approximation Algorithms and Practical Lower BoundsNate VeldtICML 2022 · 28 citations
- Correlation Clustering with Sherali-AdamsVincent Cohen-Addad, Euiwoong Lee, Alantha NewmanFOCS 2022 · 14 citations
Related papers
- A (3 + ɛ)-Approximate Correlation Clustering Algorithm in Dynamic StreamsMélanie Cambus, Fabian Kuhn, Etna Lindy, Shreyas Pai et al.SODA 2024 · 5 citations
- Local Correlation Clustering with Asymmetric Classification ErrorsJafar Jafarov, Sanchit Kalhan, Konstantin Makarychev, Yury MakarychevICML 2021 · 13 citations
- Correlation Clustering with Asymmetric Classification ErrorsJafar Jafarov, Sanchit Kalhan, Konstantin Makarychev, Yury MakarychevICML 2020 · 15 citations
- Almost 3-Approximate Correlation Clustering in Constant RoundsSoheil Behnezhad, Moses Charikar, Weiyun Ma, Li-Yang TanFOCS 2022 · 12 citations
- Query-Efficient Correlation ClusteringDavid García-Soriano, Konstantin Kutzkov, Francesco Bonchi, Charalampos E. TsourakakisWWW 2020 · 11 citations
