Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

8-2026

Abstract

Fair clustering has garnered considerable attention, with various fairness notions proposed to ensure equitable representation across demographic groups. In this paper, we focus on the k-center problem in bounded doubling metrics under two popular fairness requirements: group fairness and data summarization fairness, referred to Group Fair k-Center (Gf-k-Cen) and Data Summarization Fair k-Center (Dsf-k-Cen), respectively. Both fairness notions extend classical clustering formulation by associating each data point with a demographic label. Motivated by recent advances in parameterized approximation results for fair clustering, we investigate whether these problems admit Fixed-Parameter Tractable (FPT) approximation schemes in bounded doubling metrics. The previous algorithms typically neglect the local structural properties induced by fairness constraints itself, which limits their approximation quality. By further leveraging the geometric properties of doubling metrics together with local fairness information, we develop a candidate-based structural method that yields (1+eps)-approximation algorithms with FPT running times for both problems, parameterized by the number of selected centers. To the best of our knowledge, these results constitute the first parameterized approximation schemes for the Gf-k-Cen and Dsf-k-Cen problems in bounded doubling metrics.

Discipline

Artificial Intelligence and Robotics

Research Areas

Data Science and Engineering; Intelligent Systems and Optimization

Areas of Excellence

Digital transformation

Publication

Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence (IJCAI-26), Bremen, Germany, August 15-21

First Page

817

Last Page

825

Identifier

10.24963/ijcai.2026/92

Publisher

IJCAI

City or Country

Bremen, Germany

Additional URL

https://www.ijcai.org/proceedings/2026/92

Download

Share

COinS