Capacitated Fair-Range Clustering: Hardness and Approximation Algorithms

Capacitated fair-range $k$-clustering generalizes classical $k$-clustering by incorporating both capacity constraints and demographic fairness. In this setting, data points are categorized as clients and facilities; each facility has a capacity and may belong to one or more possibly intersecting demographic groups. The task is to select $k$ facilities as centers and assign each client to a center so that: ($a$) no center exceeds its capacity, ($b$) the number of centers selected from each group lies within specified lower and upper bounds (fair-range constraints), and ($c$) the clustering cost (e.g., $k$-median or $k$-means) is minimized. In a prior work, Thejaswi et al. (2022) showed that even satisfying fair-range constraints is NP-hard, thereby making the problem inapproximable to any polynomial factor. Our first main result strengthens this by showing that inapproximability persists even when the fair-range constraints are trivially satisfiable, highlighting the intrinsic computational complexity of the clustering task itself. These inapproximability results hold even on tree metrics and when the number of groups is logarithmic in the size of the facility set. In light of strong inapproximability results, we focus on a practical setting where the number of groups is constant. Our second main result is a polynomial-time $O(\log k)$- and $O(\log^2 k)$-approximation algorithm for $k$-median and $k$-means objectives, respectively, in this regime. Next, we design constant factor approximation algorithms for these problems that run in fixed parameterized tractable time in $k$. All our approximation guarantees match the best bounds for capacitated clustering without fair-range constraints. Finally, as our third main contribution, we show that our polynomial-time algorithms are, to our knowledge, the first to have provable approximation guarantees that can practically solve problem instances of modest size.

Multiple studies have shown that individuals at the intersection of multiple minority identities often experience compounded discrimination. Similar patterns are mirrored in algorithmic decision-making systems, yet intersectionality remains largely unaddressed in many such systems, partly because the underlying computational problems are extremely hard, making the design of practical algorithms appear out of reach. Prior works (Thejaswi et al., KDD 2022) and subsequent works on fair-range clustering (arXiv [https://arxiv.org/abs/2505.15905]), have investigated fair clustering variants in which data points belong to multiple, possibly intersecting demographic groups. In these settings, the number of selected centers from each group must lie within a prescribed lower and upper bound per group, while simultaneously minimizing a clustering objective. A key difficulty is that even finding a feasible set of cluster centers under fair-range constraints is NP-hard, making the clustering objective inapproximable to any polynomial factor. In this work, we show that even when feasibility can be checked in polynomial time, no algorithm can essentially approximate the clustering objective to non-trivial factors in time significantly better than brute force, assuming widely believed complexity conjectures. This highlights that the inapproximability arises from the intrinsic complexity of the clustering task itself, not just from the constraint satisfaction. This is especially important because, in practice, a human expert might be able to to manually select a feasible solution---but even then, finding a a good solution remains computationally intractable. We also identify restricted yet practically relevant settings that bypass these theoretical barriers. For these cases, we design practical algorithms and evaluate them extensively on both synthetic and real-world datasets. Overall, our results provide a comprehensive picture of the computational challenges and algorithmic opportunities involved in building decision-support systems that meaningfully account for intersectionality.