DROPS

Document

APPROX

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2026.13

Approximating (Weighted) Chromatic Correlation Clustering via Cluster LP

Authors: Fateme Abbasi, Hyung-Chan An, Jarosław Byrka, Changyeol Lee, and Yongho Shin

Published in: LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)

Abstract

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.

Cite as

Fateme Abbasi, Hyung-Chan An, Jarosław Byrka, Changyeol Lee, and Yongho Shin. Approximating (Weighted) Chromatic Correlation Clustering via Cluster LP. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 392, pp. 13:1-13:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{abbasi_et_al:LIPIcs.APPROX/RANDOM.2026.13,
  author =	{Abbasi, Fateme and An, Hyung-Chan and Byrka, Jaros{\l}aw and Lee, Changyeol and Shin, Yongho},
  title =	{{Approximating (Weighted) Chromatic Correlation Clustering via Cluster LP}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)},
  pages =	{13:1--13:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-449-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{392},
  editor =	{Singh, Mohit and Gur, Tom},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.13},
  URN =		{urn:nbn:de:0030-drops-277301},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2026.13},
  annote =	{Keywords: Chromatic correlation clustering, Chromatic cluster LP, Preclustering}
}

Search Results

Documents authored by Lee, Changyeol

Approximating (Weighted) Chromatic Correlation Clustering via Cluster LP

Abstract

Cite as

Thanks for your feedback!

Could not send message