Introduction
Clustering is a fundamental task in data science, typically dominated by two objectives: $k$-center (minimizing the maximum radius) and $k$-median (minimizing the sum of distances). However, $k$-center can lead to the "dissection effect," where clusters are forced into rigid, overlapping shapes because they must share the same maximum radius.
Sum of Radii (SoR) clustering provides a compelling alternative by minimizing the total sum of radii, allowing for clusters of varying sizes that more naturally fit the underlying data distribution. Despite its advantages, SoR is NP-hard. While constant-factor approximations exist, they often come with high approximation ratios or struggle when additional constraints—like fairness or matroid structures—are introduced. This paper presents a new algorithmic framework using Fixed-Parameter Tractability (FPT) to achieve significantly tighter approximation bounds for SoR and its variants.
Algorithmic Framework
The authors leverage the fact that in many practical applications, the number of clusters ($k$) is relatively small. By treating $k$ as a parameter, they develop algorithms that run in $2^{O(k \log k/\epsilon)} n^{O(1)}$ time. This approach allows for more intensive computation relative to $k$ while maintaining polynomial efficiency relative to the dataset size $n$.
Core Methodology
The approach centers on a "Radius Guessing" trick. By approximating the optimal radius profile within a factor of $(1+\epsilon)$, the problem is reduced from a continuous optimization challenge to a manageable discrete search space. The framework employs three primary strategies:
- Iterative Covering: An iterative greedy approach to cover points based on sampled radius values.
- Fairness via Matching: For Fair SoR, the algorithm converts an initial "unfair" solution into a fair one using bipartite matching.
- Matroid Intersection: For Matroid SoR, a matroid intersection subroutine handles complex structural constraints on center selection.
The fairness mechanism, as shown in Algorithm 2, involves constructing a bipartite graph between chosen centers and demographic groups. A maximum matching then dictates how to swap centers to satisfy demographic requirements without significantly increasing the total radius cost.
Key Results
The primary contribution of this work is the dramatic improvement in approximation ratios for SoR, Fair SoR, and Matroid SoR (MatSoR). By moving to the FPT setting, the authors reduce the approximation factor for standard SoR from 3.389 to $(2+\epsilon)$. Even more strikingly, for the constrained variants (Fair and Matroid), the ratio drops from $(9+\epsilon)$ to $(3+\epsilon)$.
These results demonstrate that the "cost of constraints"—the geometric penalty for shifting centers to satisfy fairness or matroid requirements—is relatively small, adding only a factor of 1 to the approximation ratio compared to the unconstrained case.
Discussion and Future Directions
While these FPT results represent a significant theoretical advance, several avenues for future research remain. The algorithms are currently randomized; while derandomization is theoretically possible, it would likely impact practical performance. Additionally, the gap between FPT and purely polynomial-time algorithms remains an open challenge. The authors also suggest exploring whether SoR admits a Quasi-Polynomial Time Approximation Scheme (QPTAS), which could potentially push approximation ratios even closer to 1.
In conclusion, by focusing on the parameter $k$, this research provides a powerful toolkit for high-precision clustering under complex real-world constraints, significantly outperforming previous state-of-the-art polynomial-time and FPT bounds.
Summary updated