Research map / Learning theory and algorithms / Clustering
Parameterized Approximation Algorithms for Sum of Radii Clustering and 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 fixed-parameter tractable constant-factor approximations for Sum of Radii clustering and its fair and matroid variants by guessing radius profiles and point assignments, using iterative covering plus bipartite matching or matroid intersection.
Problem
Sum of Radii (SoR) clustering asks for k balls centered at data points covering all points while minimizing total radius; it is NP-hard, with the best polynomial-time approximation at 3.389, and fair and matroid variants have weaker results (9+ε) in fpt time.
Approach
Guess an approximate radius profile and per-point ball assignments in fpt(k) time so SoR reduces to a k-center-like iterative covering; fairness and matroid constraints are then enforced by exchanging centers via bipartite matching or matroid intersection, yielding (2+ε) for SoR and (3+ε) for fair and matroid SoR.
Key results
- Achieves a (2+ε)-approximation for SoR in 2^{O(k log k/ε)} n^3 time with constant probability, improving the polynomial-time state of the art of 3.389.
- Achieves (3+ε)-approximation for fair SoR and matroid SoR in 2^{O(k log k/ε)} n^{O(1)} time, improving the prior (9+ε) fpt results.
- Radius profile guessing succeeds with probability at least ε^{k-1}/((k-1)^{k-1} n^2), which is repeated 2^{O(k log k/ε)} n^2 times.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed parameterized approximation framework instead of the 3.389-approximation baseline | SoR · SoR | approximation ratio: 3.389 -> 2+ε | Helped |
| Use the proposed parameterized approximation framework instead of the 9+ε-approximation baseline | FairSoR · FairSoR | approximation ratio: 9+ε -> 3+ε | Helped |
| Use the proposed parameterized approximation framework instead of the 9+ε-approximation baseline | MatSoR · MatSoR | approximation ratio: 9+ε -> 3+ε | Helped |
Limitations
- Running time is exponential in k, so only practical for small k.
- Algorithms are randomized with constant success probability per run, requiring repetition for high probability.
- No polynomial-time constant approximation for constrained SoR variants is known.
Experimental setup
Metrics: approximation ratio running time
Baselines: Friggstad and Jamshidian 2022 (3.389-approx SoR) Inamdar and Varadarajan 2020 (9+ε FairSoR and MatSoR) Charikar and Panigrahy 2004
Builds on: Friggstad and Jamshidian 2022 LP rounding Charikar and Panigrahy primal-dual Hopcroft-Karp matching Inamdar and Varadarajan 2020
Closest papers by meaning
- Improved Fixed-Parameter Bounds for Min-Sum-Radii and Diameters k-Clustering and Their Fair Variants (AAAI 2025 · similarity 0.90)
- Parameterized Approximation Algorithms for K-center Clustering and Variants (AAAI 2022 · similarity 0.88)
- Subquadratic High-Dimensional Hierarchical Clustering (NeurIPS 2019 · similarity 0.87)
- Clustering by Sum of Norms: Stochastic Incremental Algorithm, Convergence and Cluster Recovery (ICML 2017 · similarity 0.87)
- Hierarchical Clustering: $O(1)$-Approximation for Well-Clustered Graphs (NeurIPS 2021 · similarity 0.86)
- Parameterized Approximation Schemes for Fair-Range Clustering (NeurIPS 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.