Parameterized Approximation Algorithm for Doubly Constrained Fair Clustering
Authors: Xiaoliang Wu, Qilong Feng, Junyu Huang, Jianxin Wang
IJCAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we study the Fixed-Parameter Tractable (FPT) approximation algorithms for doubly constrained fair clustering under the k-median objective, referred to DFk-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. ... We theoretically prove that there must exist a (4 + ϵ)-approximation for the DF-k-MED problem, running in FPT time. |
| Researcher Affiliation | Academia | Xiaoliang Wu1,2 , Qilong Feng1 , Junyu Huang1,2 and Jianxin Wang1,2,3 1School of Computer Science and Engineering, Central South University, Changsha 410083, China 2Xiangjiang Laboratory, Changsha 410205, China 3The Hunan Provincial Key Lab of Bioinformatics, Central South University, Changsha 410083, China EMAIL, EMAIL, EMAIL, EMAIL |
| Pseudocode | Yes | Algorithm 1: An algorithm for the DF-k-MED problem Input: An instance ((X, d), F, P1, C, P2, θ, α, β, t, m, k) of the DF-k-MED problem, parameters η, γ, δ > 0 Output: A pair (H, φ) 1 Let C be the weighted set of clients constructed by Theorem 4 with ((X, d), F, C, k, η, γ) as the input, and let w : C Z+ be the corresponding weighted function; |
| Open Source Code | No | The paper does not contain any explicit statements or links indicating that source code for the described methodology is publicly available. |
| Open Datasets | No | The paper focuses on theoretical algorithm design for fair clustering and does not describe experiments using specific datasets, thus no information on open datasets is provided. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical evaluation on datasets, therefore, no dataset split information is provided. |
| Hardware Specification | No | The paper is theoretical and focuses on algorithm design and complexity analysis, without reporting on experimental results, and therefore does not specify hardware used. |
| Software Dependencies | No | The paper is theoretical and focuses on algorithm design and complexity analysis, without reporting on experimental results, and therefore does not specify software dependencies. |
| Experiment Setup | No | The paper is theoretical, presenting an approximation algorithm and its complexity analysis, and does not include empirical experiments with specific setup details or hyperparameters. |