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

Chao Chen; Chaoqi Jia; Jason Xue; Kewen Liao; Longkun Guo; Zhigang Lu

arxiv: 2601.11883 · v1 · submitted 2026-01-17 · 💻 cs.LG

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

Chaoqi Jia , Longkun Guo , Kewen Liao , Zhigang Lu , Chao Chen , Jason Xue This is my paper

Pith reviewed 2026-05-16 13:30 UTC · model grok-4.3

classification 💻 cs.LG

keywords constrained k-centerlocal searchapproximation algorithmcannot-link constraintsmust-link constraintsdominating matching set

0 comments

The pith

A local search algorithm achieves the optimal 2-approximation for constrained k-center clustering with disjoint cannot-link sets.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a local search method for k-center clustering when must-link and cannot-link constraints are given as input. By transforming the constrained instance into a dominating matching set problem, the search process finds a solution whose cost is at most twice the optimum. This ratio matches the best possible guarantee for ordinary k-center, where any improvement would imply P equals NP. The method assumes the cannot-link constraints form disjoint groups, and experiments on real and synthetic data show it returns higher-quality clusters than existing baselines.

Core claim

A novel local search framework, constructed via reduction to the dominating matching set problem, computes a 2-approximate solution for the constrained k-center problem under disjoint cannot-link constraints, matching the information-theoretic lower bound that already holds for the unconstrained version.

What carries the argument

The reduction of the constrained k-center instance to a dominating matching set problem, which permits local search swaps that preserve the factor-2 guarantee.

If this is right

The algorithm supplies the tightest possible polynomial-time guarantee for this constrained variant.
Any future improvement below ratio 2 would require proving P equals NP.
The same local-search template applies directly to any clustering task supplied with disjoint cannot-link background knowledge.
Because the ratio is optimal, no other polynomial algorithm can guarantee a strictly better worst-case performance.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

When cannot-link constraints overlap, the hardness jump may force approximation ratios to grow with the number of clusters.
The dominating-matching reduction could be reused for other objectives such as constrained k-median or k-means.
Faster practical variants might replace exhaustive local search with limited swap neighborhoods while retaining the same worst-case bound.

Load-bearing premise

The cannot-link constraints must form disjoint sets; without this restriction the problem becomes significantly harder to approximate.

What would settle it

An explicit instance with disjoint cannot-link constraints on which the local-search output exceeds twice the optimal cost.

read the original abstract

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 - {\epsilon} 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Local search reaches the tight 2-approximation for k-center under disjoint cannot-link constraints by reducing to dominating matching set.

read the letter

This paper shows that local search can achieve the optimal 2-approximation for k-center when cannot-link constraints form disjoint sets. It does so by transforming the instance into a dominating matching set problem and then applying local search, which closes the open question left by earlier constant-factor results in this setting. The reduction appears to be the main technical step, and it lets the algorithm match the unconditional hardness bound for plain k-center without extra loss factors. Experiments on real-world and synthetic data are reported to beat standard baselines in solution quality, which adds some practical grounding. The work stays within the disjoint-CL case, where constant-factor approximations were already known to exist, and it is explicit that general cannot-link constraints raise the hardness. That scoping is appropriate and avoids overclaiming. The central analysis rests on the transformation plus local search swaps, with no visible circularity or parameter fitting in the abstract description. If the full proof spells out the local search analysis cleanly, the result should stand. Minor soft spot is that experimental details like exact setup and data exclusion are not visible here, so the full version will need to make those transparent for reproducibility. This is aimed at researchers working on approximation algorithms for constrained clustering. A reader who knows standard k-center local search will see the new reduction and how it fits the existing hardness picture. It has a focused technical advance that justifies sending it to a serious referee rather than desk rejecting it.

Referee Report

0 major / 2 minor

Summary. The paper proposes a local search framework for constrained k-center clustering under disjoint cannot-link constraints. It transforms the problem to a dominating matching set problem and claims a 2-approximation ratio, matching the unconditional lower bound for k-center. Experiments on real-world and synthetic data show the algorithm outperforms baselines in solution quality.

Significance. If the central claim holds, the work resolves an open question on whether local search can achieve the optimal 2-approximation in this constrained setting. The reduction to a dominating matching set problem is a notable technical contribution that enables the tight bound while respecting disjoint CL constraints. The result is parameter-free in its approximation guarantee and includes empirical validation, strengthening its practical relevance.

minor comments (2)

[Abstract] Abstract: explicitly note that the 2-approximation holds only under the disjoint-CL assumption, as the text already acknowledges that general CL constraints raise the hardness.
[Experiments] The experimental section should include details on how cannot-link constraints are generated (e.g., number and size of disjoint sets), dataset statistics, and precise descriptions of the baseline algorithms to support reproducibility.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our work, the recognition of the technical contribution via the reduction to the dominating matching set problem, and the recommendation for minor revision. We are pleased that the optimal 2-approximation and empirical results are viewed favorably.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper derives a 2-approximation via an explicit algorithmic reduction from constrained k-center (disjoint CL case) to a dominating matching set problem followed by local search analysis. This construction is self-contained: the transformation and local-search swap rules are defined directly in the paper without reducing to fitted parameters, self-citations that carry the central claim, or ansatz smuggling. The claimed ratio matches the known unconditional k-center lower bound and is scoped to the disjoint-CL setting already known to admit constant-factor approximations. No load-bearing step collapses to a prior result by the same authors or to a definitional tautology.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result relies on standard approximation-algorithm assumptions (triangle inequality for distances, existence of optimal solution) and the domain assumption that CL constraints are disjoint; no free parameters or invented entities are introduced in the abstract.

axioms (2)

standard math Metric space satisfies triangle inequality
Implicit in k-center problem definition and approximation analysis.
domain assumption Cannot-link constraints form disjoint sets
Stated in abstract as the setting that permits constant-factor approximation.

pith-pipeline@v0.9.0 · 5473 in / 1200 out tokens · 54029 ms · 2026-05-16T13:30:17.823923+00:00 · methodology