Capacitated Fair-Range Clustering: Hardness and Approximation Algorithms

Ameet Gadekar, Suhas Thejaswi · 2025

Read Capacitated Fair-Range Clustering: Hardness and Approximation Algorithms by Ameet Gadekar, Suhas Thejaswi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-15905.txt.

Introduction

Gadekar and Thejaswi study fair grouping of clients around a set of centers in twenty twenty-five. Each center can serve only a set number of clients and may belong to one or more social groups. Planners must pick centers so each group gets a fair share of them. At the same time, total travel cost should stay as low as can be.

Past work showed the fair rule alone makes the task very hard. The new work shows the task stays hard even when the fair rule is easy to meet. No fast method can do well in the broad case. When the number of groups is small and fixed, they give methods with proven bounds.

Catalog record

CREATORAmeet Gadekar, Suhas Thejaswi
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE120 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-15905

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Capacitated Fair-Range Clustering: Hardness and Approximation Algorithms Thanks: Authors listed in alphabetical order. Ameet Gadekar, Suhas Thejaswi Abstract Capacitated fair-range k k -clustering generalizes classical k k -clustering by incorporating both capacity constraints and demographic fairness. In this setting, data points are categorized as clients and facilities, where each facility has a capacity limit and may belong to one or more possibly intersecting demographic groups. The task is to select k k facilities as centers and assign each client to a center such that: ( a a ) no center exceeds its capacity, ( b b ) the number of centers selected from each group lies within specified lower and upper bounds—defining the fair-range constraints, and ( c c ) the clustering cost— e.g. , k k -median or k k -means—is minimized. Prior work by Thejaswi et al. (KDD 2022) showed that even satisfying fair-range constraints is 𝖭𝖯 \mathsf{NP} -hard, thereby making the problem inapproximable to any polynomial factor. We strengthen this result by showing that inapproximability persists even when the fair-range constraints are trivially satisfiable, highlighting the intrinsic computational complexity of the clustering task itself. Assuming standard complexity-theoretic conjectures, we further show that no non-trivial approximation is possible without exhaustively enumerating all k k -subsets of the facility set. Notably, our inapproximability results hold even on tree metrics and even when the number of groups is logarithmic in the size of the facility set. In light of these strong inapproximability results, we focus our attention to a more practical setting where the number of groups is constant. In this regime, we design two approximation algorithms: ( i i ) a polynomial-time 𝖮 ⁡ ( log ⁡ k ) \mathsf{O}(\log k) - and 𝖮 ⁡ ( log 2 ⁡ k ) \mathsf{O}(\log^{2}k) -approximation algorithm for the k k -median and k k -means objectives, and ( i ​ i ii ) a fixed-parameter tractable algorithm parameterized by k k , achieving ( 3 + ϵ ) (3+\epsilon) - and ( 9 + ϵ ) (9+\epsilon) -approximation, respectively. These results match the best-known approximation guarantees for capacitated clustering without fair-range constraints and resolves an open question posed by Zang et al. (NeurIPS 2024). 1 Introduction Clustering is the task of partitioning a set of data points into clusters by choosing k representative points, known as cluster centers (or simply centers, when the context is clear), and assigning each data point to a center to form a clustering solution. The quality of a clustering solution is typically measured using clustering cost, most commonly defined by the k -median (or k -means) objective, where the goal is to minimize the sum of (squared) distances between each data point and its assigned center. In a more general setting, data points are distinguished as clients and facilities—which may or may not overlap—with a constraint that cluster centers must be chosen from the set of facilities. Further, in capacitated clustering, each facility is also associated with a capacity that limits the number of clients that can be assigned to it. Here, the task is to choose k centers and assign clients to centers in a way that does not exceed their capacities, while minimizing the clustering cost. In real-world applications, data points can be associated with attributes such as sex, education level, or language skills, forming possibly intersecting groups corresponding to these attributes. In this setting, and with the growing focus on algorithmic fairness, clustering problems that require selecting centers from different demographic groups have been studied under the umbrella of fair clustering [ 1 ] . This line of work, specifically addressing cluster center fairness, has introduced several problem formulations that impose lower bounds, upper bounds, or equality constraints on the number of centers chosen from each group [ 2 , 3 , 4 , 5 , 6 ] A more general variant, known as fair-range clustering that has both lower and upper bounds on the number of centers chosen from each group [ 7 , 8 , 9 ] . While prior efforts have primarily focused on fairness in uncapacitated settings, many real-world applications often impose capacity limitations for cluster centers, which is the focus of our work. To further motivate the relevance of studying this setting, consider a university mentorship initiative to support incoming students from diverse academic, socioeconomic, and cultural backgrounds. The program aims to assign each student (client) to a mentor (facility) who will serve as their primary point of contact for guidance. Each mentor has a limited capacity—they can support only a fixed number of students due to time constraints—and mentors belong to one or more demographic groups— e.g. , based on sex, country of origin, or academic discipline—forming possibly intersecting groups. To ensure the program to be effective, the university should solve a clustering task: ( i ) assigning students to mentors based on shared academic goals or proximity in fields of study (minimizing a clustering objective), ( ii ) respecting mentor capacity limits, and ( iii ) ensuring diversity in mentor selection— e.g. , ensuring representation from women, international faculty, or underrepresented scientific disciplines. This example highlights a broader class of real-world (clustering) problems where diversity, capacity, and proximity must all be considered when designing algorithmic decision-support systems. Such problems can be formalized as the capacitated fair-range clustering problem, where the goal is to select k centers from a set of facilities and assign each client to a center such that the number of clients assigned to each center does not exceed its capacity ( capacity constraints ), and ensure that the number of centers selected from each group lies within specified lower and upper bounds ( fair-range constraints ). The clustering objective can be k -median or k -means, resulting in the capacitated fair-range k -median or capacitated fair-range k -means problem. In light of the growing interest in fair clustering, there has been remarkable progress towards understanding the computational complexity as well as design of algorithms for these problems, both in polynomial-time and fixed-parameter tractable ( FPT ) setting. 1 1 1 Informally, a (parameterized) problem P is fixed-parameter tractable (approximable) if there exists an algorithm that for any instance (x,k)\in P computes an exact (approximate) solution in time f(k)\cdot|x|^{\mathsf{O}(1)} , for some computable f ; k is called the parameter of the problem. We denote by \textsf{FPT}(k) for such running times. When the groups are disjoint, polynomial-time approximation algorithms are known for fair-range clustering [ 7 ] . However, when the groups intersect, Thejaswi et al. [ 5 ] showed 2 2 2 In fact, their reduction produces instances with lower-bound only requirements. However, our results can be extended to produce instances with lower-bound only requirements. See Appendix A for details. that the problem is inapproximable to any multiplicative factor. A key insight in their result is that, with intersecting groups, even satisfying the fair-range constraints becomes \mathsf{NP} -hard regardless of the clustering objective to be optimized. As a consequence, the fair-range k -median ( k -means) problem is inapproximable to any multiplicative factor, both in polynomial-time and in \textsf{FPT}(k) -time, even for structured inputs such as Euclidean and tree metrics. Naturally, these results extend to the capacitated variants of these fair-range clustering problems,

Read the complete text