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

AI summary

Overview

• Research area: Unsupervised and semi-supervised machine learning, specifically approximation algorithms for constrained clustering (metric k-center with cannot-link and must-link constraints), with a theoretical computer science core (NP-hardness, approximation ratios, local search).
• Technical level: Advanced.
• Scope: The paper designs and analyzes a local search algorithm that transforms constrained k-center clustering into a "dominating matching set" problem and proves a best-possible 2-approximation, backed by experiments on three UCI datasets and a synthetic dataset.

What This Paper Is About

The classic k-center clustering problem asks for k centers that minimize the largest distance between any data point and its nearest center, and it is known that no polynomial-time algorithm can beat a ratio of 2 unless P = NP. This paper studies the harder version where the data comes with background knowledge in the form of cannot-link constraints (points that must not share a cluster) and must-link constraints (points that must share a cluster), and asks whether a local search method can still guarantee a constant-factor approximation. The authors answer yes for disjoint cannot-link sets, giving an algorithm whose solution quality matches the best ratio achievable for the unconstrained problem.

Key Contributions

1. A threshold-based local search algorithm for k-center with cannot-link and must-link constraints that transforms the constrained k-center problem into a dominating matching set (DMS) problem on an auxiliary l-partite graph.
2. A proof that the best possible 2-approximation is attainable for constrained k-center with disjoint cannot-link constraints, achieved through a structure called the single-swap free dominating matching set (SF-DMS) and local search, which can be computed in polynomial time.
3. A hardness result showing that computing a minimum DMS is NP-hard — even when every CL set has size 1 and points lie on a 2-dimensional plane — and admits no EPTAS under the exponential time hypothesis, which motivates the use of the weaker but tractable SF-DMS.
4. Extensive experiments on three real-world datasets and a synthetic dataset showing the method (LSCKC) outperforms baselines in clustering cost and empirical approximation ratio under both disjoint and intersected cannot-link constraints.

Main Findings

• Best possible ratio for the constrained problem: The local search framework achieves an approximation ratio of 2 for constrained k-center, matching the theoretical lower bound for the unconstrained problem, since any improvement to 2 − ε would imply P = NP.
• Open question answered: The paper states that whether local search can deliver a constant-factor guarantee for disjoint cannot-link sets was previously an open question; this work resolves it affirmatively.
• Minimum DMS is intractable: Even when |Y_i| = 1 for all i and points lie on a 2-dimensional plane, computing a minimum DMS is NP-hard and admits no EPTAS under the exponential time hypothesis (Proposition 6, building on Marx 2007). A minimal DMS is polynomial-time computable but insufficient to approximate the problem; the SF-DMS is both polynomial-time computable and sufficient.
• Bound on the number of centers: For an SF-DMS Γ of the auxiliary l-partite graph with respect to distance 2·opt, |Γ| ≤ k_𝒴, where k_𝒴 is the number of optimal clusters containing points from the union of the CL sets (Lemma 8).
• Termination with at most k centers: The grand algorithm returns a center set C with |C| ≤ k when the threshold η ≥ 2·opt, where opt is the optimal radius (Theorem 9).
• Runtime guarantee: The grand algorithm runs in O(n²k^4.5) time (Lemma 10).
• Optimal radius is a data distance: The optimal radius opt must equal the distance between some pair of points in the dataset, so it can be found by searching over the set Ψ = {d_ij} of pairwise distances rather than computed exactly up front (Lemma 11).
• Empirical performance: The abstract and introduction report that the algorithm outperforms baselines in solution quality and consistently beats baselines under both disjoint and intersected CL constraints; the detailed numerical cost comparisons in Section 4.2 are cut off in the provided content and are not reported here.

Methodology in Plain English

The algorithm is built in stages, working with a distance threshold set to twice the (unknown) optimal radius.

1. Pretend the optimal radius is known. Setting a threshold of 2·opt makes it possible to reason about which points could share a center, and the paper later shows that the same 2-approximation guarantee holds without knowing opt, by searching over the pairwise distances in the dataset.

2. Handle must-link groups first. Each must-link set is treated like a single "big point," and an existing threshold-based procedure (Algorithm 1, from Guo et al.) selects centers for these groups while ignoring the cannot-link sets.

3. Represent cannot-link relationships as a graph. The disjoint cannot-link sets are turned into an auxiliary l-partite graph, where an edge between two points from different CL sets exists only if their distance is within the threshold. A good set of centers in this graph is a "dominating matching set" — a set that can be matched to all remaining points of every CL set at the required distance.

4. Find a good center set by local search. Because finding the smallest DMS is NP-hard, the algorithm starts from any feasible center set (possibly larger than k) and repeatedly applies an "enhanced single swap": add one point as a center and remove two existing centers, as long as the result still validly covers all CL-constrained points at the threshold and respects the constraints. When no such swap exists, the set is single-swap free (SF-DMS), and the proof shows it contains at most k centers at radius 2·opt.

5. Combine the two parts. The final algorithm merges the must-link centers with the cannot-link centers found by local search, and the analysis confirms the total number of centers stays within k.

6. Test it. The method, named LSCKC, is compared against two heuristics (Greedy_H, Matching_H) and an approximation algorithm (Approx, from Guo et al. 2024) on three UCI datasets (Cnae-9, Skin, Covertype) and a synthetic dataset with k = 50, measuring clustering cost and running time. Constraints are constructed following Guo et al. (2025). Experiments vary the proportion of constrained points for disjoint CL/ML, and for intersected CL/ML they first select 10% of points and then sample x% of those points with x% ranging from 0% to 50%. Each configuration is repeated at least 20 times and averages are reported. All algorithms were implemented in Java 1.8.0 and run on an Apple M1 Max CPU with 32 GB of RAM.

Why This Matters

• Impact on research: The work closes a gap between what was previously achievable only through other techniques (such as the reverse dominating set approach of Guo et al. 2024) and what local search can guarantee, showing that local search — a general and widely used optimization technique — is sufficient to reach the optimal approximation ratio for constrained k-center with disjoint cannot-link sets. It also provides a clean transformation from a constrained clustering problem to a combinatorial structure (the DMS) with hardness and tractability results on both sides.
• Real-world applications (drawn from the paper's motivation):
  • Online customer segmentation, where groups of customers must be separated or kept together based on known business rules.
  • Recommendation systems, where background knowledge about items or users imposes grouping constraints.
  • Trip planning, where minimizing the furthest traveling distance is the objective.
  • Document summarization, where the largest dissimilarity between documents matters, and semi-supervised learning where labels propagate better when clustering respects pairwise constraints.
• Industry relevance: Because the method guarantees a solution within twice the optimal radius while keeping the number of centers within k, it is usable in settings where practitioners have partial supervisory information (from domain experts or existing labels) and need clusters that honor that knowledge without paying a large price in cluster quality. The authors release code at https://github.com/ChaoqiJia/LSCKC.

Future Directions

• Beyond disjoint cannot-link sets: The approximation guarantee is proved for disjoint CL constraints; the experiments also cover intersected CL constraints, but a matching theoretical guarantee for the intersected case remains an open direction.
• Reducing the runtime: The current bound is O(n²k^4.5), driven by the O(nk²) swap pairs examined per iteration in the local search stage; faster implementations or improved analysis could enable larger datasets.
• Closing the gap between minimum DMS and SF-DMS: Since minimum DMS is NP-hard and admits no EPTAS, understanding whether other polynomial-time computable structures could give the same or stronger guarantees is a natural question.
• Broadening empirical evaluation: The paper notes that details on clustering runtime and experiments with varying k will appear in the full version, suggesting further empirical work across more datasets, constraint types, and values of k.

Target Audience

Researchers and graduate students in theoretical computer science, approximation algorithms, and machine learning who work on clustering, semi-supervised learning, or combinatorial optimization; also suitable for practitioners who need clustering methods that respect known pairwise constraints while retaining provable quality guarantees, provided they are comfortable with the underlying algorithmic analysis.

Authors’ 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 - ε 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.