Research map / Learning theory and algorithms / Clustering
Improved Fixed-Parameter Bounds for Min-Sum-Radii and Diameters k-Clustering and Their Fair Variants
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 an exact n^O(k) algorithm for metric min-sum-diameters (improving n^O(k^2)), (1+eps) FPT-PTAS approximations for MSR/MSD and variants (fair, mergeable, outliers, alpha-MSR, k-center) in doubling metrics, and matching ETH lower bounds.
Problem
Min-sum-radii and min-sum-diameters clustering with a fixed number of clusters k in general and doubling metrics, including fair, mergeable, outlier and alpha-power variants.
Approach
Bounds the number of neighboring clusters per cluster (neighborhood size at most 4) so witnesses per cluster are constant, giving n^O(k) exact MSD; combines net-based decomposition with recursive ball-covering search for (1+eps) approximations with (1/eps)^O(kd) time.
Key results
- Exact MSD in general metrics in n^O(k) time, improving previous n^O(k^2).
- (1+eps)-approximation for MSR and MSD in time min{O(kn), 2^O(d) n log n} + (1/eps)^O(kd) in doubling metrics.
- ETH lower bound: MSR cannot be solved in n^o(k) time, and MSD admits no 2^o(k) algorithm.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Improve metric MSD exact algorithm from n^{O(k^2)} to n^{O(k)} | Exact MSD · Metric MSD | running time: n^{O(k^2)} -> n^{O(k)} | Helped |
| Use the proposed approximation instead of the previous metric MSR approximation | Metric MSR · Metric MSR | approximation ratio: (2+\epsilon) -> (1+\epsilon) | Helped |
| Use the proposed approximation instead of the previous metric MSD approximation | Metric MSD · Metric MSD | approximation ratio: (6+\epsilon) -> (1+\epsilon) | Helped |
| Use the proposed approximation instead of the previous Fair MSR approximation | Fair MSR · Fair MSR | approximation ratio: (3+\epsilon) -> (1+\epsilon) | Helped |
| Restrict witness count per MSD cluster using the bounded-neighborhood property | Exact MSD · Metric MSD | running time: n^{O(k^2)} -> n^{O(k)} | Helped |
Surprising findings
- MSR brute-force n^O(k) is optimal under ETH, even in constant doubling dimension.
Limitations
- Running times are exponential in k and d, so only practical for small k and low doubling dimension.
- Approximation schemes rely on the decomposition and netting machinery, which has large constants.
Experimental setup
Metrics: running time approximation factor
Baselines: brute-force n^O(k^2) MSD algorithm (3+eps)-approximation for MSR (6+eps)-approximation for MSD
Builds on: point hierarchy (nets) decomposability framework primal-dual rounding for outliers Grid Tiling ETH hardness
Closest papers by meaning
- Parameterized Approximation Algorithms for Sum of Radii Clustering and Variants (AAAI 2024 · similarity 0.90)
- Relax and Merge: A Simple Yet Effective Framework for Solving Fair $k$-Means and $k$-sparse Wasserstein Barycenter Problems (ICLR 2025 · similarity 0.87)
- New Bounds on the Cohesion of Complete-link and Other Linkage Methods for Agglomerative Clustering (ICML 2024 · similarity 0.87)
- Competitively Consistent Clustering (ICML 2025 · similarity 0.87)
- Parameterized Approximation Schemes for Fair-Range Clustering (NeurIPS 2024 · similarity 0.86)
- Beyond Worst-Case Coreset Bounds for $k$-Clustering via Determinantal Sampling (NeurIPS 2026 · 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.