Abstract
This paper introduces a novel $(4 + \epsilon)$-approximation algorithm for the "doubly constrained" fair clustering problem. Unlike previous methods where computational complexity scales with the number of demographic groups, this approach is "color-agnostic." By leveraging submodular maximization and matroid constraints, the algorithm achieves a runtime of $FPT(k)$, effectively decoupling the process from the number of demographic labels and providing a scalable solution for high-dimensional demographic data.
Introduction
Clustering is a fundamental task in data science, aimed at grouping similar items together. However, traditional clustering objectives often fail to account for demographic representation, potentially leading to biased outcomes. To address this, researchers have proposed two primary fairness paradigms:
- Group Fairness: Ensures each cluster reflects the demographic composition of the overall population.
- Data Summarization Fairness: Ensures the selected cluster centers (facilities) are themselves demographically diverse.
While these constraints have been studied in isolation, many real-world applications require both simultaneously, leading to the "doubly constrained" fair clustering problem. Previous algorithms for this task were typically parameterized by the number of demographic groups (colors), making them computationally prohibitive as the number of categories (e.g., age, gender, ethnicity) increases. This research addresses this "curse of dimensionality" by proposing an algorithm whose complexity depends only on the number of facilities ($k$).
Methodology
The authors propose a two-phase, color-agnostic structural method for the Doubly Constrained Fair $k$-Median (DF-$k$-MED) problem.
Phase 1: Finding Feasible Facilities
The algorithm first employs a coreset technique to reduce the dataset into a manageable set of representative points. It then identifies "leaders"—clients likely to be proximal to optimal facilities—and discretizes their potential distances.
Crucially, the facility selection is modeled as a monotone submodular maximization problem under two partition matroid constraints. One constraint ensures a facility is selected near each leader, while the other satisfies the data summarization fairness requirements. This formulation allows the algorithm to handle fairness as a structural property of the set rather than iterating through every color combination.
Phase 2: Solving the Weighted Assignment
Once facilities are established, the algorithm must assign clients to them to satisfy group fairness. This is modeled as a Weighted Assignment Problem and solved using Linear Programming (LP). To maintain efficiency, the authors use a deterministic rounding method that converts the fractional LP solution into an integer assignment. This process allows for a minimal violation of at most one point per constraint.
Key Results
The primary contribution of this work is the achievement of a constant-factor approximation with a runtime independent of the number of demographic labels ($m$ and $t$).
As shown in the table above, the algorithm provides a $(4 + \epsilon)$-approximation. While the approximation ratio is slightly higher than single-constraint methods, the runtime complexity is significantly improved to $FPT(k)$, or $f(k, \epsilon)n^{O(1)}$. This represents a major advancement for practical applications where $k$ is small but the number of demographic combinations is large.
Discussion and Future Work
While the algorithm provides a robust theoretical framework, it introduces a fairness violation of at most 1. In certain high-stakes contexts, even minor deviations from strict parity may be problematic. Achieving a similar approximation ratio with zero violation in $FPT(k)$ time remains an open challenge.
Additionally, while the runtime is independent of the number of colors, it remains exponential in $k$. Future research could investigate if tighter approximation ratios are possible within specific metric spaces, such as Euclidean space ($R^d$), or if the dependency on $k$ can be further optimized. As a theoretical contribution, this work does not include empirical testing, leaving the practical performance on large-scale datasets as a subject for future study.
Summary updated