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+\varepsilon)$-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.
From: Changyeol Lee [view email]
[v1]
Wed, 15 Oct 2025 11:46:49 UTC (24 KB)
[v2]
Tue, 14 Jul 2026 02:56:53 UTC (36 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。