2025-11-10T02:53:59.476691

Chromatic correlation clustering via cluster LP

Abbasi, An, Byrka et al.
Correlation Clustering is a fundamental clustering problem, and there has been a line of work on improving the approximation ratio for this problem in recent years. A key algorithmic component in these works is the cluster LP. Chromatic Correlation Clustering is an interesting generalization that has also been intensively studied. In light of success of the cluster LP in Correlation Clustering, it would be an interesting question whether the cluster LP can be used in Chromatic Correlation Clustering. We answer this question with affirmatives by presenting a $(2+\varepsilon)$-approximation algorithm for Chromatic Correlation Clustering using a chromatic cluster LP.
academic

Chromatic correlation clustering via cluster LP

基本信息

  • 论文ID: 2510.13446
  • 标题: Chromatic correlation clustering via cluster LP
  • 作者: Fateme Abbasi, Hyung-Chan An, Jarosław Byrka, Changyeol Lee, Yongho Shin
  • 分类: cs.DS (Data Structures and Algorithms)
  • 发表时间: 2025年10月15日 (arXiv预印本)
  • 论文链接: https://arxiv.org/abs/2510.13446

摘要

相关聚类(Correlation Clustering)是一个基础的聚类问题，近年来在改进该问题的近似比方面有一系列工作。这些工作中的关键算法组件是cluster LP。彩色相关聚类(Chromatic Correlation Clustering)是一个有趣的推广，也得到了深入研究。鉴于cluster LP在相关聚类中的成功，一个有趣的问题是cluster LP是否可以用于彩色相关聚类。本文通过提出一个使用彩色cluster LP的(2+ε)(2+\varepsilon)-近似算法来肯定地回答这个问题。

研究背景与动机

问题背景

  1. 相关聚类问题：相关聚类是组合优化和机器学习领域的基础问题，目标是将顶点划分为若干簇，使得正边(+边)的端点在同一簇内，负边(-边)的端点在不同簇内。
  2. 彩色相关聚类：这是相关聚类的推广，其中每条正边都有一个颜色标签，同一簇内的顶点必须通过相同颜色的边连接。
  3. 研究动机：
    • 近年来相关聚类的近似比不断改进，从最初的3近似提升到目前的1.437近似
    • cluster LP是这些改进的关键技术组件
    • 彩色相关聚类的现有方法局限于色盲算法、归约到标准相关聚类或使用标准LP松弛
    • 最新的2.15近似算法仍基于归约方法

研究意义

探索cluster LP技术能否直接应用于彩色相关聚类，以获得更好的近似比，这对理论和实践都具有重要意义。

核心贡献

  1. 提出彩色cluster LP：设计了相关聚类中cluster LP的自然推广版本，适用于彩色相关聚类问题
  2. 多项式时间求解：证明了彩色cluster LP可以在多项式时间内近似最优求解
  3. 2近似舍入算法：设计了将彩色cluster LP的可行解舍入为整数解的算法，近似比为2
  4. (2+ε)(2+\varepsilon)-近似算法：结合上述两个结果，得到了彩色相关聚类的(2+ε)(2+\varepsilon)-近似算法，改进了之前的2.15近似
  5. 预聚类技术：将相关聚类中的预聚类(preclustering)概念推广到彩色情况，这是实现多项式时间求解的关键

方法详解

任务定义

输入：

  • 颜色集合 LL
  • 完全图，每条边标记为+边或-边
  • 每条+边 ee 关联一个颜色 ce∈Lc_e \in L

输出：

  • 顶点划分 CC
  • 着色函数 χ:C→L\chi: C \to L，为每个簇分配颜色

目标：最小化不一致边的数量，其中不一致边定义为：

  • -边的两端在同一簇内
  • +边的两端在不同簇内
  • +边的两端在同一簇内，但簇的颜色与边的颜色不匹配

彩色Cluster LP

核心的线性规划松弛定义为：

min⁡∑S⊆V,ℓ∈L(∣δ+(S)∣2+∣E−ℓ[S]∣)zSℓ\min \sum_{S\subseteq V,\ell\in L} \left(\frac{|\delta^+(S)|}{2} + |E^{-\ell}[S]|\right) z^\ell_S

约束条件： ∑S∋v,ℓ∈LzSℓ=1,∀v∈V\sum_{S\ni v,\ell\in L} z^\ell_S = 1, \quad \forall v \in VzSℓ≥0,∀S⊆V,∀ℓ∈Lz^\ell_S \geq 0, \quad \forall S \subseteq V, \forall\ell \in L

其中：

  • zSℓz^\ell_S 表示集合SS是否为颜色ℓ\ell的簇
  • δ+(S)\delta^+(S) 是跨越SS的+边集合
  • E−ℓ[S]E^{-\ell}[S] 是SS内除ℓ\ell色+边外的所有边集合

算法框架

第一步：预聚类构造

  1. 使用常数近似算法获得初始解(Cinit,χinit)(C^{init}, \chi^{init})
  2. 标记满足特定条件的顶点（基于参数α,β\alpha, \beta）
  3. 构造预聚类KK和颜色分配χpre\chi^{pre}

第二步：有界子cluster LP

  1. 将搜索空间限制在大小不超过r=Θ(ε−12)r = \Theta(\varepsilon^{-12})的簇
  2. 构造多项式大小的LP并求解

第三步：Monte Carlo采样

  1. 从LP解中采样Δy∅\Delta y_\emptyset个着色簇
  2. 使用Raghavendra-Tan舍入算法
  3. 构造最终的可行解

关键技术创新

  1. 彩色预聚类：
    • 将预聚类概念推广到彩色情况
    • 证明最优解必须尊重预聚类结构
    • 控制可容许边的数量为O(ε−2)optO(\varepsilon^{-2})\text{opt}
  2. 基于簇的舍入算法：
    • 设计了专门的概率舍入过程
    • 分析了不同类型边成为不一致的概率
    • 证明了2倍近似比

实验设置

本文是理论计算机科学论文，主要贡献在于算法设计和理论分析，没有包含实验评估部分。研究重点在于：

  1. 理论分析：证明算法的正确性和近似比
  2. 复杂度分析：证明算法的多项式时间复杂度
  3. 数学证明：通过严格的数学推导验证结果

实验结果

主要理论结果

定理 3.2：给定彩色cluster LP的可行解，基于簇的算法输出的整数解期望代价至多是LP解代价的2倍。

定理 4.3：存在多项式时间算法构造预聚类实例，满足：

  • 存在代价至多(1+O(ε))opt(1+O(\varepsilon))\text{opt}的尊重解
  • 可容许边数量∣Eadm∣≤O(ε−2)opt|E_{adm}| \leq O(\varepsilon^{-2})\text{opt}

主要结果：彩色相关聚类存在(2+ε)(2+\varepsilon)-近似算法，改进了之前的2.15近似。

复杂度分析

  • 预聚类构造：O(n2)O(n^2)时间
  • LP求解：poly(n,ε−1)\text{poly}(n, \varepsilon^{-1})时间
  • Monte Carlo采样：nO(ε−12)n^{O(\varepsilon^{-12})}时间

相关工作

相关聚类研究

  1. 经典结果：Bansal等人的3近似算法
  2. 近期进展：通过cluster LP技术将近似比改进到1.437
  3. 关键技术：Sherali-Adams层次结构、预聚类技术

彩色相关聚类研究

  1. 色盲算法：忽略颜色信息的方法
  2. 归约方法：转化为标准相关聚类问题
  3. LP舍入：基于标准LP松弛的舍入算法
  4. 最新结果：Lee等人的2.15近似和1.64近似算法

本文贡献

相比现有工作，本文首次将cluster LP技术直接应用于彩色相关聚类，避免了归约的损失。

结论与讨论

主要结论

  1. 彩色cluster LP可以在多项式时间内近似求解
  2. 存在2倍近似的舍入算法
  3. 整体获得(2+ε)(2+\varepsilon)-近似算法，改进了现有最好的2.15近似

局限性

  1. 时间复杂度：虽然是多项式时间，但指数依赖于ε−1\varepsilon^{-1}
  2. 近似比：仍有改进空间，与标准相关聚类的1.437近似存在差距
  3. 实用性：缺乏实验验证算法的实际性能

未来方向

  1. 探索是否能达到与标准相关聚类相同的近似比
  2. 改进算法的时间复杂度
  3. 研究两个问题之间近似比的理论分离

深度评价

优点

  1. 理论创新：首次将cluster LP技术成功应用于彩色相关聚类
  2. 技术深度：预聚类技术的推广具有很高的技术难度
  3. 结果改进：在理论上改进了现有最好结果
  4. 证明严谨：数学分析完整且严格

不足

  1. 实验缺失：作为算法论文，缺乏实验验证
  2. 复杂度较高：算法的实际运行时间可能很长
  3. 改进有限：从2.15到2的改进相对较小
  4. 适用性：方法的推广性有待进一步验证

影响力

  1. 理论贡献：为彩色相关聚类提供了新的技术路径
  2. 方法论：cluster LP技术的推广具有方法论价值
  3. 后续研究：为进一步改进近似比奠定了基础

适用场景

  1. 理论研究：为近似算法理论提供新的案例
  2. 实际应用：适用于需要考虑边颜色约束的聚类问题
  3. 算法设计：为相关优化问题提供技术参考

参考文献

论文引用了24篇重要文献，主要包括：

  1. Bansal, Blum, Chawla (2004) - 相关聚类的奠基工作
  2. Cao等人 (2024) - 1.437近似算法
  3. Cohen-Addad等人 (2023) - 预聚类技术
  4. Lee等人 (2025) - 彩色相关聚类的最新结果
  5. Raghavendra, Tan (2012) - 舍入算法技术

这些文献构成了本文研究的重要理论基础和技术支撑。