2026-09-10T09:44:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27730 2026-09-09T12:19:35Z ddc:004 open_access

Approximating (Weighted) Chromatic Correlation Clustering via Cluster LP Abbasi, Fateme An, Hyung-Chan Byrka, Jarosław Lee, Changyeol Shin, Yongho Chromatic correlation clustering Chromatic cluster LP Preclustering Correlation Clustering is a fundamental clustering problem that is generalized to Chromatic Correlation Clustering to incorporate categorical data. Both problems have been intensively studied, and recently, substantial improvements were obtained in the approximation algorithms for Correlation Clustering. At the heart of this success lies a new linear program (LP) formulation called the cluster LP; a natural question was whether this LP can be extended to Chromatic Correlation Clustering to enable similar success. We answer this question in the affirmative by presenting a (2+ε)-approximation algorithm for the problem using a chromatic cluster LP. We then consider Weighted Chromatic Correlation Clustering, in which edges have fractional weights satisfying the probability constraints, to show that our algorithm extends to this weighted version to yield the same approximation guarantee. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Fateme Abbasi and Hyung-Chan An and Jarosław Byrka and Changyeol Lee and Yongho Shin 2026 Is Part Of LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2026.13 urn:nbn:de:0030-drops-277301 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.13 eng https://creativecommons.org/licenses/by/4.0/legalcode