Research map / Learning theory and algorithms / Clustering
Global Optimization of K-Center Clustering
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add FBBT bounds tightening to closed-form BB (ablation) | reduced-space BB for k-center · SYN-3002 synthetic | time (s): 46 s to 12 s | Helped |
| add FBBT bounds tightening to closed-form BB (ablation) | reduced-space BB for k-center · AADP2 (14M samples) | gap (%): 55.91% gap to ≤0.1% gap | Helped |
| use BB with closed-form lower bound and FBBT instead of direct CPLEX | k-center on large datasets · synthetic and real datasets | gap / UB: CPLEX+Q fails to reach ≤0.1% gap on most datasets over 740 samples | Helped |
| use farthest first traversal heuristic instead of global BB | k-center clustering · 32 datasets | UB: global optimum reduces objective by 30.4% on average vs FFT (BEST) | Hurt |
| add initial seeds from FFT for cluster assignment (vs symmetry breaking) (ablation) | BB+CF+FBBT · real-world datasets | nodes: fewer nodes when initial seeds found | Helped |
| add FBBT to closed-form BB on AADP2 (UB quality) (ablation) | BB+CF+FBBT · AADP2 (14M samples) | UB: UB 2660.10 to 2546.92 | Helped |
| add FBBT to BB on AC2 dataset (ablation) | BB+CF+FBBT · AC2 (7195 samples) | UB: UB 2.75 to 2.78 | Hurt |
Closest papers by meaning
- Efficient Constrained K-center Clustering with Background Knowledge (AAAI 2024 · similarity 0.91)
- Almost Optimal Fully Dynamic $k$-Center Clustering with Recourse (ICML 2025 · similarity 0.88)
- Approximately Pareto-optimal Solutions for Bi-Objective k-Clustering (NeurIPS 2024 · similarity 0.88)
- Dynamic k-center clustering with lifetimes (NeurIPS 2026 · similarity 0.87)
- Improved Guarantees for Fully Dynamic $k$-Center Clustering with Outliers in General Metric Spaces (NeurIPS 2024 · similarity 0.87)
- Towards a Theoretical Understanding of Why Local Search Works for Clustering with Fair-Center Representation (AAAI 2024 · similarity 0.86)
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.