Research map / Learning theory and algorithms / Clustering
A Scalable Deterministic Global Optimization Algorithm for Clustering Problems
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 sample grouping to the reduced-space BB bounds (BBClst+SG vs BBClst+CF) (ablation) | BB clustering algorithm · Synthetic Syn-42000 (k=3) | GAP(%): 9.82 -> 5.43 | Helped |
| Add sample grouping to the reduced-space BB bounds (BBClst+SG vs BBClst+CF) (ablation) | BB clustering algorithm · Iris (k=3) | GAP(%): 50.76 -> 1.58 | Helped |
| Add Lagrangian decomposition on top of sample grouping (ablation) | BB clustering algorithm · Syn-1200 (k=4) and Syn-2100 (k=4) | GAP(%): Syn-1200 k=4: 12.26 -> 20.81; Syn-2100 k=4: 12.41 -> 25.14 (worse); Syn-2100 k=3: 3.20 -> 2.71 (better) | Mixed |
| Use closed-form basic bounds only (BBClst+CF) instead of sample grouping and Lagrangian decomposition (ablation) | BB clustering algorithm · Synthetic Syn-300 (k=3) | GAP(%): 7.31 vs 0.88 (SG) vs <0.1 (LD+SG) | Hurt |
| Parallelize BBClst+LD+SG across CPU cores (20 cores vs serial) (ablation) | BB clustering algorithm · Syn-300 (k=3) | time to GAP <0.1%: 2h serial -> 0.4h on 20 cores | Helped |
| Replace CPLEX classic BB with the proposed reduced-space BB (BBClst+LD+SG) | MSSC global optimization · Syn-42000 (k=3) | feasible solution found: CPLEX no feasible solution vs BBClst UB 501472.82 | Helped |
| Replace CPLEX classic BB with the proposed BB (BBClst+LD+SG) for gap reduction | MSSC global optimization · Iris (k=3) | GAP(%): 328.63 -> 0.1 | Helped |
| Scale to 210,000 samples with 200-core parallel BB (BBClst+LD+SG) | MSSC global optimization · Syn-210000 (k=3) | GAP(%): 2.55 final gap | Helped |
Closest papers by meaning
- Global Optimization of K-Center Clustering (ICML 2022 · similarity 0.90)
- Scalable and Globally Optimal Generalized L₁ K-center Clustering via Constraint Generation in Mixed Integer Linear Programming (AAAI 2023 · similarity 0.88)
- Efficient Algorithms for Sum-Of-Minimum Optimization (ICML 2024 · similarity 0.86)
- Beyond Worst-Case Coreset Bounds for $k$-Clustering via Determinantal Sampling (NeurIPS 2026 · similarity 0.86)
- Improved Fixed-Parameter Bounds for Min-Sum-Radii and Diameters k-Clustering and Their Fair Variants (AAAI 2025 · similarity 0.86)
- Statistically Optimal $K$-means Clustering via Nonnegative Low-rank Semidefinite Programming (ICLR 2024 · similarity 0.85)
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.