Approximation Algorithm for Constrained k-Center Clustering: A Local Search Approach¶

会议: AAAI 2026
arXiv: 2601.11883
代码: https://github.com/ChaoqiJia/LSCKC
领域: 理论算法 / 聚类 / 近似算法
关键词: k-center 聚类, 约束聚类, 局部搜索, 近似比, cannot-link, must-link, dominating matching set

一句话总结¶

研究带 cannot-link (CL) 和 must-link (ML) 实例级约束的 k-center 聚类问题，提出基于支配匹配集（dominating matching set, DMS）转化的局部搜索框架，在不相交 CL 集条件下首次通过局部搜索达到最优近似比 2，解决了该领域一个开放问题。

研究背景与动机¶

k-center 是聚类和数据分析的基础理论问题：给定 n 个数据点和正整数 k，选 k 个中心使任意点到最近中心的最大距离最小化。标准 k-center 的最优近似比为 2（Gonzalez 1985; Hochbaum & Shmoys 1985），任何 \(2-\epsilon\) 近似都意味着 \(\mathcal{P}=\mathcal{NP}\)。

在半监督学习和实际应用中，背景知识常以实例级约束给出： - Cannot-link (CL)：两个点不能在同一簇，如冲突关系建模 - Must-link (ML)：两个点必须在同一簇，如标签传播

理论困难：一般 CL 约束会导致不可近似——找到满足所有 CL 约束的聚类本身就是 NP-hard（通过 k-着色问题归约）。但 Guo et al. (2024) 发现：当 CL 集不相交时（即 CL 集互不共享点），仍可达常数因子近似比 2。然而他们使用的是反向支配集（RDS）构造，局部搜索能否在此设定下达到最优近似比 2 一直是开放问题。

方法详解¶

整体框架¶

三阶段算法（Algorithm 3）： 1. Stage 1(a)：忽略 CL 约束，用阈值算法（Algorithm 1）找处理 ML 约束的中心集 \(C_1\) 2. Stage 1(b)：为 CL 集找候选中心 \(C_2\)，使 \(C_1 \cup C_2\) 覆盖所有 CL 约束点。对每个 CL 集 \(Y_i\) 构建二部图并找最大匹配，未匹配的 CL 点加入候选 3. Stage 2：对 \(C_2\) 执行局部搜索（Algorithm 2），通过增强单交换（enhanced single swap）操作缩减中心数量到 ≤k

关键设计¶

问题转化为 DMS：将 CL 约束表示为辅助 l-部图 \(G_\mathcal{Y}\)，CL 集点为顶点，不同 CL 集间距离 ≤ η 的点对为边。在此图上定义支配匹配集（DMS）——中心集 Γ 需保证每个 CL 集 Y 中，Γ∖Y 与 Y∖Γ 之间存在阈值最大匹配，匹配大小恰好为 |Y∖Γ|
单交换自由 DMS（SF-DMS）：最小 DMS 是 NP-hard 的（即使 |Y_i|=1 且点在平面上），但 SF-DMS 可多项式时间计算。SF-DMS 满足：对任意 p ∈ V 和 {u,v} ⊆ Γ，Γ∪{p}∖{u,v} 不再是 DMS——即无法通过加一个点换两个来改进
核心引理（Lemma 8）：SF-DMS 的大小 |Γ| ≤ k_Y，其中 k_Y 是最优解中包含 CL 点的簇数。这保证了局部搜索终止时中心数量 ≤ k
不依赖已知 opt：通过 Lemma 11 观察到 opt 必在某对点的距离中取得，遍历候选距离值找最小可行阈值

复杂度¶

算法运行时间 \(O(n^2 k^{4.5})\)：Stage 1(a) \(O(kn)\)，Stage 1(b) \(O(nk^{3/2})\)（Hopcroft-Karp 匹配），Stage 2 局部搜索 \(O(k)\) 轮 × \(O(nk^2)\) 交换对 × \(O(nk^{1.5})\) 可行性检查。

实验关键数据¶

主实验：经验近似比（合成数据集 k=50）¶

算法	平均经验近似比	最大近似比	理论保证
Greedy_H	最高	>2	无
Matching_H	较高	>2	无
Approx (Guo et al.)	中等	<2	2-近似
LSCKC（本文）	最低	<2	2-近似

真实数据集聚类代价（k=30，不相交 CL/ML 约束）¶

数据集	约束比	LSCKC 代价	Approx 代价	优势
Cnae-9	2%-10%	最低	较高	约束越多优势越明显
Skin	2%-10%	最低	较高	显著优于所有基线
Covertype	2%-10%	最低	较高	稳定领先

关键发现¶

LSCKC 在所有约束比（2%-10%）和重复比（10%-50%）下均达到最低聚类代价
随约束数量增加，所有算法的近似比趋于上升（可行域缩小），但 LSCKC 的增速最慢
局部搜索的 swap 步骤能从非约束点中探索更好的中心——这是基线 Approx 无法做到的
在交叉 CL 约束场景下（虽然理论不保证），LSCKC 仍表现出色
在 Cnae-9 数据集上，约束越多 LSCKC 优势越明显——附加约束限制了 Approx 的解空间，但局部搜索可从非约束点选中心
实验配置：Java 1.8.0，Apple M1 Max CPU，32GB RAM，每组设置重复至少 20 次取平均

亮点与洞察¶

解决开放问题：首次证明局部搜索能在不相交 CL 约束的 k-center 中达到最优近似比 2，回答了 Guo et al. (2024) 留下的开放问题
DMS 转化的优雅性：将约束聚类转化为图上的支配匹配集，使局部搜索可以利用匹配理论工具。最小 DMS 是 NP-hard 的，但 SF-DMS 是多项式可计算的——这个"恰好够用的结构"是理论贡献的核心
增强单交换：不同于标准局部搜索的 1-swap，这里是加 1 个点换 2 个点的 enhanced swap，提供了更强的搜索能力
归纳证明的精巧：Lemma 8 的证明通过 Case(a) 和 Case(b) 分析最优簇的覆盖情况，利用反证法和子问题递归得到 |Γ| ≤ k_Y

局限性¶

限于不相交 CL 集：当 CL 集有交叉（共享点）时，理论保证不成立，虽然实验表现仍好
运行时间 \(O(n^2 k^{4.5})\)：对大规模数据集（n 很大）可能偏慢，最大匹配计算是瓶颈
k-center 的本质局限：对异常值敏感（最大距离目标），实际中 k-median 或 k-means 可能更实用
实验仅在 3 个 UCI 数据集 + 合成数据上验证，规模较小
未探索将 DMS 框架推广到其他约束聚类变体（如 k-means with CL/ML）的可能性

评分¶

新颖性: ⭐⭐⭐⭐ 解决开放问题，DMS 转化方法新颖
实验充分度: ⭐⭐⭐ 理论工作为主，实验为辅助验证
写作质量: ⭐⭐⭐⭐ 问题动机和证明思路清晰
价值: ⭐⭐⭐ 对理论算法社区有价值，应用面较窄

工作	约束类型	方法	近似比	k 的范围
Davidson et al. 2010	CL+ML	SAT-based	\((1+\epsilon)\)	k=2
Brubach et al. 2021	仅 ML	—	2	一般 k
Guo et al. 2024	不相交 CL	反向支配集 (RDS)	2	一般 k
本文	不相交 CL + ML	局部搜索 (DMS)	2	一般 k