{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T06:16:07Z","timestamp":1774419367306,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":42,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,6,10]],"date-time":"2024-06-10T00:00:00Z","timestamp":1717977600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Villum Fonden","award":["16582"],"award-info":[{"award-number":["16582"]}]},{"name":"Independent Research Fund Denmark","award":["Starting Grant 1054-00032B"],"award-info":[{"award-number":["Starting Grant 1054-00032B"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,6,10]]},"DOI":"10.1145\/3618260.3649712","type":"proceedings-article","created":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T19:25:02Z","timestamp":1718133902000},"page":"1617-1628","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Combinatorial Correlation Clustering"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0779-8962","authenticated-orcid":false,"given":"Vincent","family":"Cohen-Addad","sequence":"first","affiliation":[{"name":"Google Research, Paris, France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8835-0926","authenticated-orcid":false,"given":"David Rasmussen","family":"Lolck","sequence":"additional","affiliation":[{"name":"University of Copenhagen, Copenhagen, Denmark"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5680-7397","authenticated-orcid":false,"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"University of Warsaw, Warsaw, Poland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5237-1709","authenticated-orcid":false,"given":"Mikkel","family":"Thorup","sequence":"additional","affiliation":[{"name":"University of Copenhagen, Copenhagen, Denmark"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9439-8942","authenticated-orcid":false,"given":"Shuyi","family":"Yan","sequence":"additional","affiliation":[{"name":"University of Copenhagen, Copenhagen, Denmark"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3149-7799","authenticated-orcid":false,"given":"Hanwen","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of Copenhagen, Copenhagen, Denmark"}]}],"member":"320","published-online":{"date-parts":[[2024,6,11]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1498759.1498824"},{"key":"e_1_3_2_1_2_1","volume-title":"Proceedings of the 32nd International Conference on Machine Learning (ICML). 2237\u20132246","author":"Ahn Kook Jin","year":"2015","unstructured":"Kook Jin Ahn, Graham Cormode, Sudipto Guha, Andrew McGregor, and Anthony Wirth. 2015. Correlation Clustering in Data Streams. In Proceedings of the 32nd International Conference on Machine Learning (ICML). 2237\u20132246."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1411509.1411513"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.43"},{"key":"e_1_3_2_1_5_1","volume-title":"Proceedings of the 13th Conference on Innovations in Theoretical Computer Science (ITCS) (LIPIcs","volume":"20","author":"Assadi Sepehr","year":"2022","unstructured":"Sepehr Assadi and Chen Wang. 2022. Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions. In Proceedings of the 13th Conference on Innovations in Theoretical Computer Science (ITCS) (LIPIcs, Vol. 215). 10:1\u201310:20."},{"key":"e_1_3_2_1_6_1","volume-title":"Correlation clustering. Machine learning, 56, 1","author":"Bansal Nikhil","year":"2004","unstructured":"Nikhil Bansal, Avrim Blum, and Shuchi Chawla. 2004. Correlation clustering. Machine learning, 56, 1 (2004), 89\u2013113."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00074"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.CH33"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch33"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00032"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-012-0522-9"},{"key":"e_1_3_2_1_12_1","volume-title":"International Conference on Machine Learning (ICML). 1136\u20131146","author":"Bun Mark","year":"2021","unstructured":"Mark Bun, Marek Elias, and Janardhan Kulkarni. 2021. Differentially private correlation clustering. In International Conference on Machine Learning (ICML). 1136\u20131146."},{"key":"e_1_3_2_1_13_1","volume-title":"Massively Parallel Correlation Clustering in Bounded Arboricity Graphs. In 35th International Symposium on Distributed Computing (DISC) (LIPIcs","volume":"18","author":"Cambus M\u00e9lanie","year":"2021","unstructured":"M\u00e9lanie Cambus, Davin Choo, Havu Miikonen, and Jara Uitto. 2021. Massively Parallel Correlation Clustering in Bounded Arboricity Graphs. In 35th International Symposium on Distributed Computing (DISC) (LIPIcs, Vol. 209). 15:1\u201315:18."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.101"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2307.06723"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367549"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","unstructured":"Sayak Chakrabarty and Konstantin Makarychev. 2023. Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple!. In Advances in Neural Information Processing Systems (NeurIPS). https:\/\/doi.org\/10.48550\/ARXIV.2305.13560 arXiv:2305.13560. 10.48550\/ARXIV.2305.13560","DOI":"10.48550\/ARXIV.2305.13560"},{"key":"e_1_3_2_1_18_1","unstructured":"Sayak Chakrabarty and Konstantin Makarychev. 2023. Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple!. arXiv preprint arXiv:2305.13560."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.10.012"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-006-0210-9"},{"key":"e_1_3_2_1_21_1","volume-title":"Proceedings of the 47th annual ACM Symposium on Theory of Computing (STOC). 219\u2013228","author":"Chawla Shuchi","year":"2015","unstructured":"Shuchi Chawla, Konstantin Makarychev, Tselil Schramm, and Grigory Yaroslavtsev. 2015. Near optimal LP rounding algorithm for correlation clustering on complete and complete k-partite graphs. In Proceedings of the 47th annual ACM Symposium on Theory of Computing (STOC). 219\u2013228."},{"key":"e_1_3_2_1_22_1","unstructured":"Yudong Chen Sujay Sanghavi and Huan Xu. 2012. Clustering sparse graphs. In Advances in Neural Information Processing Systems (Neurips). 2204\u20132212."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623743"},{"key":"e_1_3_2_1_24_1","volume-title":"Proceedings of 62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS). 468\u2013479","author":"Cohen-Addad Vincent","year":"2021","unstructured":"Vincent Cohen-Addad, Debarati Das, Evangelos Kipouridis, Nikos Parotsidis, and Mikkel Thorup. 2021. Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor. In Proceedings of 62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS). 468\u2013479."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Vincent Cohen-Addad Chenglin Fan Silvio Lattanzi Slobodan Mitrovic Ashkan Norouzi-Fard Nikos Parotsidis and Jakub Tarnawski. 2022. Near-Optimal Correlation Clustering with Privacy. In Advances in Neural Information Processing Systems (Neurips).","DOI":"10.1109\/FOCS54457.2022.00068"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00035"},{"key":"e_1_3_2_1_27_1","volume-title":"Proceedings of International Conference on Machine Learning (ICML). 4157\u20134179","author":"Cohen-Addad Vincent","year":"2022","unstructured":"Vincent Cohen-Addad, Silvio Lattanzi, Andreas Maggiori, and Nikos Parotsidis. 2022. Online and Consistent Correlation Clustering. In Proceedings of International Conference on Machine Learning (ICML). 4157\u20134179."},{"key":"e_1_3_2_1_28_1","volume-title":"Proceedings of the 38th International Conference on Machine Learning (ICML). 2069\u20132078","author":"Cohen-Addad Vincent","year":"2021","unstructured":"Vincent Cohen-Addad, Silvio Lattanzi, Slobodan Mitrovic, Ashkan Norouzi-Fard, Nikos Parotsidis, and Jakub Tarnawski. 2021. Correlation Clustering in Constant Many Parallel Rounds. In Proceedings of the 38th International Conference on Machine Learning (ICML). 2069\u20132078."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00065"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00068"},{"key":"e_1_3_2_1_31_1","volume-title":"Marcin Pilipczuk, Mikkel Thorup, Shuyi Yan, and Hanwen Zhang.","author":"Cohen-Addad Vincent","year":"2024","unstructured":"Vincent Cohen-Addad, David Rasmussen Lolck, Marcin Pilipczuk, Mikkel Thorup, Shuyi Yan, and Hanwen Zhang. 2024. Combinatorial Correlation Clustering. arxiv:2404.05433."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.05.008"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2006.v002a013"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2008.78"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536458"},{"key":"e_1_3_2_1_36_1","unstructured":"Silvio Lattanzi Benjamin Moseley Sergei Vassilvitskii Yuyan Wang and Rudy Zhou. 2021. Robust Online Correlation Clustering. In Advances in Neural Information Processing Systems (Neurips). 4688\u20134698."},{"key":"e_1_3_2_1_37_1","volume-title":"Better Private Algorithms for Correlation Clustering. CoRR, arXiv abs\/2202.10747","author":"Liu Daogao","year":"2022","unstructured":"Daogao Liu. 2022. Better Private Algorithms for Correlation Clustering. CoRR, arXiv abs\/2202.10747 (2022)."},{"key":"e_1_3_2_1_38_1","volume-title":"Proceedings of 27th International Symposium on Theoretical Aspects of Computer Science (STACS). 573\u2013584","author":"Mathieu Claire","year":"2010","unstructured":"Claire Mathieu, Ocan Sankur, and Warren Schudy. 2010. Online Correlation Clustering. In Proceedings of 27th International Symposium on Theoretical Aspects of Computer Science (STACS). 573\u2013584."},{"key":"e_1_3_2_1_39_1","volume-title":"Jordan","author":"Pan Xinghao","year":"2015","unstructured":"Xinghao Pan, Dimitris S. Papailiopoulos, Samet Oymak, Benjamin Recht, Kannan Ramchandran, and Michael I. Jordan. 2015. Parallel Correlation Clustering on Big Graphs. In Advances in Neural Information Processing Systems (Neurips). 82\u201390."},{"key":"e_1_3_2_1_40_1","volume-title":"Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 526\u2013527","author":"Swamy Chaitanya","year":"2004","unstructured":"Chaitanya Swamy. 2004. Correlation Clustering: Maximizing agreements via semidefinite programming.. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 526\u2013527."},{"key":"e_1_3_2_1_41_1","volume-title":"International Conference on Machine Learning (ICML). 22060\u201322083","author":"Veldt Nate","year":"2022","unstructured":"Nate Veldt. 2022. Correlation Clustering via Strong Triadic Closure Labeling: Fast Approximation Algorithms and Practical Lower Bounds. In International Conference on Machine Learning (ICML). 22060\u201322083."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178876.3186110"}],"event":{"name":"STOC '24: 56th Annual ACM Symposium on Theory of Computing","location":"Vancouver BC Canada","acronym":"STOC '24","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 56th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649712","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3618260.3649712","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:03:52Z","timestamp":1750291432000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649712"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,10]]},"references-count":42,"alternative-id":["10.1145\/3618260.3649712","10.1145\/3618260"],"URL":"https:\/\/doi.org\/10.1145\/3618260.3649712","relation":{},"subject":[],"published":{"date-parts":[[2024,6,10]]},"assertion":[{"value":"2024-06-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}