{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T22:57:36Z","timestamp":1781305056911,"version":"3.54.1"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032286901","type":"print"},{"value":"9783032286918","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-28691-8_6","type":"book-chapter","created":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T22:33:53Z","timestamp":1781303633000},"page":"81-96","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["1.64-Approximation for Chromatic Correlation Clustering via Chromatic Cluster LP"],"prefix":"10.1007","author":[{"given":"Chenglin","family":"Fan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dahoon","family":"Lee","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Euiwoong","family":"Lee","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,6,13]]},"reference":[{"key":"6_CR1","unstructured":"Abbasi, F., An, H., Byrka, J., Lee, C., Shin, Y.: Chromatic correlation clustering via cluster LP (2025). https:\/\/arxiv.org\/abs\/2510.13446"},{"key":"6_CR2","doi-asserted-by":"publisher","unstructured":"Ailon, N., Charikar, M., Newman, A.: Aggregating Inconsistent Information: Ranking and Clustering, vol.\u00a055. Association for Computing Machinery, New York, NY, USA (2008). https:\/\/doi.org\/10.1145\/1411509.1411513","DOI":"10.1145\/1411509.1411513"},{"key":"6_CR3","doi-asserted-by":"publisher","unstructured":"Anava, Y., Avigdor-Elgrabli, N., Gamzu, I.: Improved theoretical and practical guarantees for chromatic correlation clustering. In: Proceedings of the 24th International Conference on World Wide Web, WWW 2015, pp. 55\u201365. International World Wide Web Conferences Steering Committee, Republic and Canton of Geneva, CHE (2015). https:\/\/doi.org\/10.1145\/2736277.2741629","DOI":"10.1145\/2736277.2741629"},{"key":"6_CR4","unstructured":"Assadi, S., Wang, C.: Sublinear time and space algorithms for correlation clustering via sparse-dense decompositions. In: Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS), pp. 10:1\u201310:20 (2022)"},{"issue":"1\u20133","key":"6_CR5","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1023\/B:MACH.0000033116.57574.95","volume":"56","author":"N Bansal","year":"2004","unstructured":"Bansal, N., Blum, A., Chawla, S.: Correlation clustering. Mach. Learn. 56(1\u20133), 89\u2013113 (2004). https:\/\/doi.org\/10.1023\/B:MACH.0000033116.57574.95","journal-title":"Mach. Learn."},{"key":"6_CR6","doi-asserted-by":"crossref","unstructured":"Bateni, M., et al.: Optimal fully dynamic k-center clustering for adaptive and oblivious adversaries. In: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2677\u20132727 (2023)","DOI":"10.1137\/1.9781611977554.ch101"},{"key":"6_CR7","doi-asserted-by":"crossref","unstructured":"Behnezhad, S., Charikar, M., Ma, W., Tan, L.: Almost 3-approximate correlation clustering in constant rounds. In: 63rd IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 720\u2013731 (2022)","DOI":"10.1109\/FOCS54457.2022.00074"},{"key":"6_CR8","doi-asserted-by":"crossref","unstructured":"Behnezhad, S., Charikar, M., Ma, W., Tan, L.: Single-pass streaming algorithms for correlation clustering. In: Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 819\u2013849 (2023)","DOI":"10.1137\/1.9781611977554.ch33"},{"key":"6_CR9","doi-asserted-by":"publisher","unstructured":"Ben-Dor, A., Yakhini, Z.: Clustering gene expression patterns. In: Proceedings of the Third Annual International Conference on Computational Molecular Biology, RECOMB 1999, pp. 33\u201342. Association for Computing Machinery, New York, NY, USA (1999). https:\/\/doi.org\/10.1145\/299432.299448","DOI":"10.1145\/299432.299448"},{"key":"6_CR10","doi-asserted-by":"publisher","unstructured":"Bonchi, F., Gionis, A., Gullo, F., Tsourakakis, C.E., Ukkonen, A.: Chromatic correlation clustering. ACM Trans. Knowl. Discov. Data 9(4) (2015). https:\/\/doi.org\/10.1145\/2728170","DOI":"10.1145\/2728170"},{"key":"6_CR11","unstructured":"Braverman, V., Dharangutte, P., Pai, S., Shah, V.: Fully dynamic adversarially robust correlation clustering in polylogarithmic update time. In: Proceedings of the 28th International Conference on Artificial Intelligence and Statistics (AISTATS) (2025)"},{"key":"6_CR12","doi-asserted-by":"publisher","unstructured":"Cao, N., et al.: Solving the correlation cluster LP in sublinear time. In: Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, pp. 1154\u20131165. Association for Computing Machinery, New York, NY, USA (2025). https:\/\/doi.org\/10.1145\/3717823.3718181","DOI":"10.1145\/3717823.3718181"},{"key":"6_CR13","unstructured":"Cao, N., et al.: Static to dynamic correlation clustering. CoRR abs\/2504.12060 (2025)"},{"key":"6_CR14","doi-asserted-by":"publisher","unstructured":"Cao, N., Cohen-Addad, V., Lee, E., Li, S., Newman, A., Vogl, L.: Understanding the cluster linear program for correlation clustering. In: Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, pp. 1605\u20131616. Association for Computing Machinery, New York, NY, USA (2024). https:\/\/doi.org\/10.1145\/3618260.3649749","DOI":"10.1145\/3618260.3649749"},{"key":"6_CR15","doi-asserted-by":"publisher","unstructured":"Charikar, M., Guruswami, V., Wirth, A.: Clustering with qualitative information. J. Comput. Syst. Sci. 71(3), 360\u2013383 (2005). https:\/\/doi.org\/10.1016\/j.jcss.2004.10.012, learning Theory 2003","DOI":"10.1016\/j.jcss.2004.10.012"},{"key":"6_CR16","doi-asserted-by":"crossref","unstructured":"Chawla, S., Makarychev, K., Schramm, T., Yaroslavtsev, G.: 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), pp. 219\u2013228 (2015)","DOI":"10.1145\/2746539.2746604"},{"key":"6_CR17","unstructured":"Cohen-Addad, V., Hjuler, N., Parotsidis, N., Saulpic, D., Schwiegelshohn, C.: Fully dynamic consistent facility location. In: Proceedings of the 33rd Annual Conference on Neural Information Processing Systems (NeurIPS) (2019)"},{"key":"6_CR18","unstructured":"Cohen-Addad, V., Lattanzi, S., Maggiori, A., Parotsidis, N.: Online and consistent correlation clustering. In: Proceedings of the 39th International Conference on Machine Learning (ICML), pp. 4157\u20134179 (2022)"},{"key":"6_CR19","unstructured":"Cohen-Addad, V., Lattanzi, S., Maggiori, A., Parotsidis, N.: Dynamic correlation clustering in sublinear update time. In: Proceedings of the 41st International Conference on Machine Learning (ICML), pp. 9230\u20139270 (2024)"},{"key":"6_CR20","unstructured":"Cohen-Addad, V., Lattanzi, S., Mitrovic, S., Norouzi-Fard, A., Parotsidis, N., Tarnawski, J.: Correlation clustering in constant many parallel rounds. In: Proceedings of the 38th International Conference on Machine Learning (ICML), vol. 139, pp. 2069\u20132078 (2021)"},{"key":"6_CR21","doi-asserted-by":"publisher","unstructured":"Cohen-Addad, V., Lee, E., Li, S., Newman, A.: Handling correlated rounding error via preclustering: a 1.73-approximation for correlation clustering. In: 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pp. 1082\u20131104 (2023). https:\/\/doi.org\/10.1109\/FOCS57990.2023.00065","DOI":"10.1109\/FOCS57990.2023.00065"},{"key":"6_CR22","doi-asserted-by":"publisher","unstructured":"Cohen-Addad, V., Lee, E., Newman, A.: Correlation Clustering with Sherali-Adams . In: 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 651\u2013661. IEEE Computer Society, Los Alamitos, CA, USA (2022). https:\/\/doi.org\/10.1109\/FOCS54457.2022.00068","DOI":"10.1109\/FOCS54457.2022.00068"},{"key":"6_CR23","unstructured":"Dalirrooyfard, M., Makarychev, K., Mitrovic, S.: Pruned pivot: correlation clustering algorithm for dynamic, parallel, and local computation models. CoRR abs\/2402.15668 (2024). https:\/\/doi.org\/10.48550\/arXiv.2402.15668"},{"key":"6_CR24","doi-asserted-by":"publisher","unstructured":"Fan, C., Lee, D., Lee, E.: Improved approximation algorithms for chromatic and pseudometric-weighted correlation clustering. CoRR abs\/2505.21939v2 (2025). https:\/\/doi.org\/10.48550\/ARXIV.2505.21939, to appear at NeurIPS 2025","DOI":"10.48550\/ARXIV.2505.21939"},{"key":"6_CR25","unstructured":"Fichtenberger, H., Mirrokni, V., Zadimoghaddam, M.: Correlation clustering in data streams. In: Proceedings of the 33rd Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) (2021)"},{"key":"6_CR26","unstructured":"Guo, A., Mitrovic, S., Vassilvitskii, S.: Distributed correlation clustering. In: Advances in Neural Information Processing Systems (NeurIPS) (2021)"},{"key":"6_CR27","unstructured":"Jaghargh, M., Vassilvitskii, S., Lattanzi, S.: Scalable correlation clustering: an empirical study. In: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (2019)"},{"key":"6_CR28","doi-asserted-by":"publisher","unstructured":"Klodt, N., Seifert, L., Zahn, A., Casel, K., Issac, D., Friedrich, T.: A color-blind 3-approximation for chromatic correlation clustering and improved heuristics. In: Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, KDD 2021, pp. 882\u2013891. Association for Computing Machinery, New York, NY, USA (2021). https:\/\/doi.org\/10.1145\/3447548.3467446","DOI":"10.1145\/3447548.3467446"},{"key":"6_CR29","unstructured":"Lattanzi, S., Vassilvitskii, S.: Consistent k-clustering. In: Proceedings of the 34th International Conference on Machine Learning (ICML), pp. 1975\u20131984 (2017)"},{"key":"6_CR30","doi-asserted-by":"publisher","unstructured":"Raghavendra, P., Tan, N.: Approximating CSPs with Global Cardinality Constraints Using SDP Hierarchies, pp. 373\u2013387 (2012). https:\/\/doi.org\/10.1137\/1.9781611973099.33","DOI":"10.1137\/1.9781611973099.33"},{"key":"6_CR31","unstructured":"Xiu, Q., Han, K., Tang, J., Cui, S., Huang, H.: Chromatic correlation clustering, revisited. In: Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 - December 9 (2022)"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-28691-8_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T22:34:00Z","timestamp":1781303640000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-28691-8_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032286901","9783032286918"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-28691-8_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"13 June 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"IPCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Integer Programming and Combinatorial Optimization","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Padua","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 June 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 June 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ipco2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/events.math.unipd.it\/ipco2026\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}