Parameterized Approximation Algorithm for Doubly Constrained Fair Clustering

Xiaoliang Wu, Qilong Feng, Junyu Huang, Jianxin Wang

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:

  1. Group Fairness: Ensures each cluster reflects the demographic composition of the overall population.
  2. 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$).

Comparison of the proposed Doubly Fair algorithm with existing single-constraint fairness methods.

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

Abstract

Fair clustering has recently received considerable attention where numerous distinct fairness notions are developed. Despite being well-justified, these fairness notions are frequently studied in isolation, leaving the need to explore how they can be combined. Building on prior work, we focus on the doubly constrained fair clustering that incorporates two widely adopted demographic representation fairness notions in clustering: group fairness and data summarization fairness. Both fairness notions extend classical clustering formulation by associating each data point with a demographic label, where group fairness requires each cluster to proportionally reflect the population-level distribution of demographic groups, and data summarization fairness ensures the chosen facilities maintaining the population-level demographic representation of each group. In this paper, we study the Fixed-Parameter Tractable (FPT) approximation algorithms for doubly constrained fair clustering under the k-median objective, referred to Df-k-Med. The previous algorithms typically enumerate different demographic groups or construct fairness coreset, parameterized by both the number of opened facilities and demographic labels. By further leveraging the local fairness information, we propose a color-agnostic structural method that obtains the parameterized result independent of the number of demographic labels while effectively handling the combination of both fairness constraints. Specifically, we design a constant factor approximation for the Df-k-Med problem with fairness violation by one, which runs in FPT(k)-time, where k is the number of opened facilities.
BibTeX
@inproceedings{wu2025parameterized,
  author = {Xiaoliang Wu and Qilong Feng and Junyu Huang and Jianxin Wang},
  title = {{Parameterized Approximation Algorithm for Doubly Constrained Fair Clustering}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/67},
}
Figure