Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2601.11883 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908994750119936 |
|---|---|
| author | Jia, Chaoqi Guo, Longkun Liao, Kewen Lu, Zhigang Chen, Chao Xue, Jason |
| author_facet | Jia, Chaoqi Guo, Longkun Liao, Kewen Lu, Zhigang Chen, Chao Xue, Jason |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_11883 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Approximation Algorithm for Constrained $k$-Center Clustering: A Local Search Approach Jia, Chaoqi Guo, Longkun Liao, Kewen Lu, Zhigang Chen, Chao Xue, Jason Machine Learning 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. |
| title | Approximation Algorithm for Constrained $k$-Center Clustering: A Local Search Approach |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2601.11883 |