{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T10:17:10Z","timestamp":1781345830487,"version":"3.54.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":"NSF CCF","award":["2008422"],"award-info":[{"award-number":["2008422"]}]},{"name":"NSF CCF","award":["2236669"],"award-info":[{"award-number":["2236669"]}]},{"name":"Google","award":[""],"award-info":[{"award-number":[""]}]},{"name":"State Key Laboratory for Novel Software Technology","award":[""],"award-info":[{"award-number":[""]}]},{"name":"New Cornerstone Science Laboratory","award":[""],"award-info":[{"award-number":[""]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,6,10]]},"DOI":"10.1145\/3618260.3649749","type":"proceedings-article","created":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T19:25:02Z","timestamp":1718133902000},"page":"1605-1616","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Understanding the Cluster Linear Program for Correlation Clustering"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4961-763X","authenticated-orcid":false,"given":"Nairen","family":"Cao","sequence":"first","affiliation":[{"name":"Boston College, Brighton, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0779-8962","authenticated-orcid":false,"given":"Vincent","family":"Cohen-Addad","sequence":"additional","affiliation":[{"name":"Google Research, Grenoble, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1454-7587","authenticated-orcid":false,"given":"Euiwoong","family":"Lee","sequence":"additional","affiliation":[{"name":"University of Michigan, Ann Arbor, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9140-9415","authenticated-orcid":false,"given":"Shi","family":"Li","sequence":"additional","affiliation":[{"name":"Nanjing University, Nanjing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-7353-7734","authenticated-orcid":false,"given":"Alantha","family":"Newman","sequence":"additional","affiliation":[{"name":"CNRS - Universit\u00e9 Grenoble Alpes, Grenoble, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8241-536X","authenticated-orcid":false,"given":"Lukas","family":"Vogl","sequence":"additional","affiliation":[{"name":"\u00c9cole polytechnique f\u00e9d\u00e9rale de Lausanne, Lausanne, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"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":"International Conference on Artificial Intelligence and Statistics. 9499\u20139516","author":"Ahmadian Sara","year":"2023","unstructured":"Sara Ahmadian and Maryam Negahbani. 2023. Improved approximation for fair correlation clustering. In International Conference on Artificial Intelligence and Statistics. 9499\u20139516."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-021-00816-9"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1411509.1411513"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.43"},{"key":"e_1_3_2_1_6_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_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2002.1181947"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132522"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00074"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch33"},{"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":"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_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.101"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.143"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367549"},{"key":"e_1_3_2_1_16_1","volume-title":"Thirty-seventh Conference on Neural Information Processing Systems.","author":"Chakrabarty Sayak","year":"2023","unstructured":"Sayak Chakrabarty and Konstantin Makarychev. 2023. Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple!. In Thirty-seventh Conference on Neural Information Processing Systems."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.10.012"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536455"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-006-0210-9"},{"key":"e_1_3_2_1_20_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_21_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_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623743"},{"key":"e_1_3_2_1_23_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_24_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_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.63"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00065"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00068"},{"key":"e_1_3_2_1_28_1","unstructured":"Sami Davies Benjamin Moseley and Heather Newman. 2023. Fast Combinatorial Algorithms for Min Max Correlation Clustering. arXiv preprint arXiv:2301.13079."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.05.008"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109624"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109686"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"e_1_3_2_1_33_1","unstructured":"Holger Heidrich Jannik Irmai and Bjoern Andres. 2023. A 4-approximation algorithm for min max correlation clustering. arXiv preprint arXiv:2310.09196."},{"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":"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_38_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_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.33"},{"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.3649749","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3618260.3649749","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.3649749"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,10]]},"references-count":42,"alternative-id":["10.1145\/3618260.3649749","10.1145\/3618260"],"URL":"https:\/\/doi.org\/10.1145\/3618260.3649749","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"}}]}}