When a Nearby Center Is Not Enough: Service-Aware Individual Fairness for Min-Sum-Radii Clustering

Neighborhood-radius individual fairness typically bounds each point's distance to the selected center set, not to the center that actually serves it. For standard pointwise objectives, nearest-center reassignment enforces fair service without increasing cost. We formalize nearest-assignment stability—coordinatewise no-farther reassignment cannot increase cost—as a sufficient transfer condition. In contrast, minimum sum of radii (MSR) depends on the realized partition and admits a linear gap: on a tree with $n=2k$ points and standard $n/k$-neighbor radii, the exact selected-set-fair and service-aware optima are $2$ and $k$, respectively. To our knowledge, we give the first study of service-aware individually fair MSR, requiring every retained point's assigned center to meet its personalized service bound. To handle this non-mergeable constraint, we introduce minimum-priority capture, which constructs centers and assignments jointly. For arbitrary priorities, the algorithm is deterministic and fixed-parameter tractable (FPT) in $k+z$ for fixed $\epsilon$. Whenever exact $\lambda$-service is feasible, it returns at most $k$ centers and at most $z$ outliers, with cost at most $(2+\epsilon )$ times the exact-service optimum and service-fairness factor $2$. We establish a matching service lower bound: for every fixed $\delta \in (0,1)$, a budget-preserving deterministic FPT algorithm guaranteeing factor $2-\delta$ on exact-service-feasible inputs would imply $\mathrm{W}[2]=\mathrm{FPT}$, even with standard neighborhood radii, no outliers, and unrestricted cost. The framework extends to fixed polynomial-time computable monotone symmetric norms of cluster radii and to min-sum-diameters.