Research map / Learning theory and algorithms / Clustering
Efficient Constrained K-center Clustering with Background Knowledge
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives the first efficient 2-approximation for k-center with must-link and cannot-link constraints by using reverse dominating sets computed via an LP primal-dual algorithm, with experiments against Greedy and Matching baselines.
Problem
k-center clustering with instance-level must-link (ML) and cannot-link (CL) background constraints is NP-hard and CL constraints make feasibility NP-complete, so prior work lacked efficient approximation guarantees beyond special cases.
Approach
Model CL sets as disjoint and build a reverse dominating set (RDS) via Hall violators; compute maximum RDS with an LP relaxation (integral basic solutions) and a fast primal-dual algorithm, contract ML sets into big points, and binary search the radius to get a 2-approximation in O(nk^3.5 log n).
Key results
- Alg. 3 achieves a proven 2-approximation and empirical approximation ratios of about 1.99-2.00 on simulated data, while Greedy and Matching reach about 2.5-3.5.
- Alg. 3 reports roughly 10% to 300% clustering quality improvement over baselines on disjoint ML/CL settings across datasets.
- Overall runtime is O(nk^3.5 log n), with the RDS primal-dual subroutine running in O(k^2.5).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the RDS-based Alg. 3 instead of Greedy or Matching | Constrained k-center · Real-world datasets with disjoint ML/CL constraints | cost | Helped |
| Use the RDS-based Alg. 3 instead of Greedy or Matching | Constrained k-center · Real-world datasets with disjoint ML/CL constraints | Normalized Mutual Information | Helped |
| Use the RDS-based Alg. 3 instead of Greedy or Matching | Constrained k-center · Real-world datasets with disjoint ML/CL constraints | Rand Index | Helped |
| Use the RDS-based Alg. 3 instead of Greedy or Matching | Constrained k-center · Real-world datasets with disjoint ML/CL constraints | runtime | Helped |
| Use the RDS-based Alg. 3 instead of Matching | Constrained k-center · Simulated datasets | approximation ratio: 2.8678 -> 1.9901 | Helped |
Surprising findings
- Alg. 3 improvement is largest on the sparse high-dimensional Cnae-9 dataset, which the authors attribute to k-center struggling on sparse data.
Limitations
- Assumes CL sets are disjoint; intersected CL constraints must be reduced, which may drop background knowledge.
- Empirical comparison only against self-constructed heuristic baselines (Greedy, Matching).
- Experiments use simulated datasets for approximation ratio since optimal costs are unknown on real data.
Experimental setup
Datasets: Wine Cnae-9 NLS-KDD Skin Wide09 Covertype Simulated
Benchmarks: Wine Cnae-9 NLS-KDD Skin Wide09 Covertype Simulated
Metrics: clustering cost (radius) NMI Rand Index log runtime empirical approximation ratio
Baselines: Greedy Matching
Builds on: k-center approximation (Hochbaum and Shmoys) COP-k-means (Wagstaff et al. 2001) Hall's marriage theorem
Closest papers by meaning
- Approximation Algorithm for Constrained k-Center Clustering: A Local Search Approach (AAAI 2026 · similarity 0.95)
- Approximately Pareto-optimal Solutions for Bi-Objective k-Clustering (NeurIPS 2024 · similarity 0.89)
- Improved Guarantees for Fully Dynamic $k$-Center Clustering with Outliers in General Metric Spaces (NeurIPS 2024 · similarity 0.89)
- Dynamic k-center clustering with lifetimes (NeurIPS 2026 · similarity 0.88)
- Competitively Consistent Clustering (ICML 2025 · similarity 0.88)
- Ultrametric Cluster Hierarchies: I Want ‘em All! (NeurIPS 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.