提出新算法解决带约束的k中心聚类，逼近比达理论最优2。
Approximation Algorithm for Constrained $k$-Center Clustering: A Local Search Approach
- 将约束聚类转化为支配匹配问题，用局部搜索求解。
- 在真实与合成数据上均优于基线，逼近比达到理论最优2。
- 适合需要严格约束且追求最优近似解的研究者使用。
聚类是人工智能与数据分析中的基础问题。传统k中心问题的最优逼近比为2，任何改进至2 - ε都意味着P = NP。本文研究带实例级不能链接（CL）和必须链接（ML）约束的k中心聚类问题，其中一般CL约束显著增加逼近难度。已有研究表明，互不相交的CL集合允许常数因子逼近。然而，局部搜索能否在该设定下实现此保证仍是未解之问。为此，我们提出一种基于支配匹配集问题转化的新型局部搜索框架，实现了最优逼近比2。在真实世界与合成数据集上的实验表明，该算法在解质量上优于基线方法。
原文摘要 · Abstract (English)
Clustering is a long-standing research problem and a fundamental tool in AI and data analysis. The traditional k-center problem, a fundamental theoretical challenge in clustering, has a best possible approximation ratio of 2, and any improvement to a ratio of 2 - ε would imply P = NP. In this work, we study the constrained k-center clustering problem, where instance-level cannot-link (CL) and must-link (ML) constraints are incorporated as background knowledge. Although general CL constraints significantly increase the hardness of approximation, previous work has shown that disjoint CL sets permit constant-factor approximations. However, whether local search can achieve such a guarantee in this setting remains an open question. To this end, we propose a novel local search framework based on a transformation to a dominating matching set problem, achieving the best possible approximation ratio of 2. The experimental results on both real-world and synthetic datasets demonstrate that our algorithm outperforms baselines in solution quality.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。