Parameterized Approximation Schemes for Fair Clustering in Doubling Metrics

1 Introduction

Clustering is a fundamental problem in machine learning with a wide range of applications in data mining, image analysis, etc. Given a set of points, the goal of clustering is to partition the point set into several disjoint clusters such that the points in the same cluster are close to each other, while points in different clusters are well separated. Several classic clustering formulations have been extensively studied, including kcenter, k-median, and k-means. In this paper, we focus on the k-center problem, in which we are given a set C of points in a metric space (X, d), and a positive integer k. The goal is to select k centers from C such that the maximum distance from any point in C to its nearest center is minimized. The k-center problem is known to be NP-hard [Garey and Johnson, 1979], and admits a 2-approximation algorithm [Gonzalez, 1985; Hochbaum and Shmoys, 1985]. Moreover, finding an optimal solution for the k-center problem is W[2]-hard if parameterized by k [Demaine et al., 2005]. Over the past decades, numerous variants of the k-center problem have been explored [Charikar et al., 2001; Aggarwal et al., 2010; Cygan et al., 2012; Chierichetti et al., 2017; Kleindessner et al., 2019; Chen et al., 2019; Mahabadi and Vakilian, 2020; Liang et al., 2025].

∗Corresponding author

Recently, fair clustering has become a major focus with many notions proposed, such as group fairness [Ahmadian et al., 2019; Bercea et al., 2019; Harb and Lam, 2020], data summarization fairness [Kleindessner et al., 2019; Jones et al., 2020], proportional fairness [Chen et al., 2019; Micha and Shah, 2020], individual fairness [Mahabadi and Vakilian, 2020; Negahbani and Chakrabarty, 2021], etc. In this paper, we focus on the k-center problem under group fairness and data summarization fairness constraints in bounded doubling metrics, denoted as Group Fair k-Center (GF-kCEN) and Data Summarization Fair k-Center (DSF-k-CEN), respectively. Motivated by recent progress on parameterized approximation algorithms for fair clustering [Bandyapadhyay et al., 2021; Thejaswi et al., 2022; Zhang et al., 2024; Wu et al., 2025], we investigate the existence of FixedParameter Tractable (FPT) approximation schemes for the GF-k-CEN and DSF-k-CEN problems in bounded doubling metrics (an approximation scheme is a (1+ε)-approximation algorithm, where ε is an arbitrary small constant). In both fairness settings, each point is assigned a color indicating its demographic group. The two notions differ in how fairness is enforced: group fairness imposes the composition of each cluster such that the number of points with each color respects pre-specified proportions, whereas data summarization fairness requires the selected centers such that the number of centerswith each colormatches a pre-specified value. Indeed, both fairness notions extend the classical clustering formulation with demographic labels, where the former requires each cluster to proportionally reflect the population-level distribution of demographic groups, and the latter ensures the chosen centers maintaining the population-level demographic representation of each group. We briefly illustrate the motivation for these notions. As noted in [Chierichetti et al., 2017], if minority groups are ignored during the clustering process, the resulting clusters may substantially distort their representation, leading to systematically unfair outcomes. Data summarization similarly aims to select a small subset that represents the whole dataset. However, without fairness constraints, such summaries can be biased with respect to sensitive attributes. For instance, the Google Images search results for the query "CEO" have been shown to over-represent men relative to their real-world prevalence, reinforcing harmful stereotypes [Kay et al., 2015].

[Chierichetti et al., 2017] introduced the definition of fairness with only two colors, requiring that the proportion of two colors has approximately equal representation in each cluster. [Bercea et al., 2019] formalized group fairness more generally, and presented a 3-approximation with an additive 1 violation of the group fairness constraints for the GF-kCEN problem, using linear programming and min-cost flow network. The violation value represents the extent to which the fairness constraints are violated. [Ahmadian et al., 2019] studied the GF-k-CEN problem with only an upper bound constraint, obtaining a 3-approximation with an additive 2 violation (under a notion of violation different from [Bercea et al., 2019]), again via linear programming and min-cost flow network. When colors are allowed to overlap, a 4approximation algorithm with (4∆ + 3) violation [Bera et al., 2019] and a 3-approximation algorithm with (4∆ + 3) violation [Harb and Lam, 2020] were given for the GF-kCEN problem, respectively, where ∆ is the maximum number of colors to which any point may belong. Regarding parameterized result, [Goyal and Jaiswal, 2023] proposed a 2-approximation for the GF-k-CEN problem in FPT(k,m)- time, where m is the number of colors (nO(1) f(k) time for an input size of n and a positive function f , denoted by FPT(k)- time for brevity). [Bandyapadhyay et al., 2021] employed the fair coreset technique to obtain (3 + ε)-approximation and (9 + ε)-approximation for the k-median and k-means objectives under group fairness constraints, respectively, both in FPT(k, m)-time.

[Kleindessner et al., 2019] presented a (3 · 2m-1 - 1)- approximation with running time O(nkm2 + km4 ) based on a swap technique for the DSF-k-CEN problem. [Jones et al., 2020] improved the time complexity to O(nk), and maintained the approximation factor 3 by maximum matching method. More recently, [Angelidakis et al., 2022] considered the lower-bounded version of the DSF-k-CEN problem, and gave a 15-approximation algorithm in time O(nk2 +k5 ). [Thejaswi et al., 2022] extended data summarization fairness by introducing an additional lower-bound constraint on the number of selected centers, and provided (1 + 2/e + ε)- approximation and (1 + 8/e + ε)-approximation for the kmedian and k-means objectives, respectively, both running in FPT(k,m)-time. Moreover, the approximation factor can be further improved to (1 + ε) in Euclidean space [Zhang et al., 2024]. [Wu et al., 2025] considered the doubly constrained fairness setting that combines group fairness and data summarization fairness constraints under the k-median objective, and gave a (4 + ε)-approximation algorithm of fairness violation by one in FPT(k)-time.

For the GF-k-CEN and DSF-k-CEN problems, several fundamental obstacles hinder the development of improved approximation algorithms. The FPT approximation algorithm in [Goyal and Jaiswal, 2023] for the GF-k-CEN problem starts with a bi-criteria approximate solution with O(k log n) centers. However, the gap between the bi-criteria solution and the optimal solution remains large, making it difficult to refine the solution to achieve better approximation guarantee. Moreover, for the k-center problem, it is known that achieving an approximation factor better than 2 is NP-hard unless P=NP [Hsu and Nemhauser, 1979]. Therefore, for the GF-k-CEN and DSF-k-CEN problems, the gaps between the ratios of the previous results and the lower bound ratio of kcenter are still large. A common paradigm underlying existing algorithms for both problems is to first compute a set of k initial clustering centers and then convert it into a feasible solution. Unfortunately, even when the set of k initial clustering centers is of high-quality, converting it into a solution that satisfies the fairness constraints while incurring only a small loss in approximation guarantee remains troublesome, as this process often discards effective local structural information induced by the fairness constraints itself. Indeed, for the GF-k-CEN problem, even assigning data points to a fixed set of centers under fairness constraints is NP-hard [Esmaeili et al., 2021]. Consequently, how to effectively convert a set of initial clustering centers to a desired feasible solution (the gap between the approximate solution obtained by the set of initial clustering centers and the optimal solution is small) is still a challenge for the GF-k-CEN and DSF-k-CEN problems. The hardness result of [Goyal and Jaiswal, 2023] shows that no FPT(k)-time algorithm can achieve an approximation ratio better than 2 for the GF-k-CEN problem in general metric spaces. Nevertheless, this negative result does not rule out the possibility of better approximation guarantees in more structured settings. In particular, their analysis applies only to general metrics, and leaves open the potential for improved approximation algorithms in restricted metric spaces such as doubling metrics. This naturally motivates the question of whether effective FPT time approximation schemes can be developed for the GF-k-CEN and DSF-k-CEN problems in such structured settings.

1.1 Our Contributions

In this paper, we take the first step toward exploiting the structural properties of doubling metrics for the GF-k-CEN and DSF-k-CEN problems, and propose a candidate-based structural method to overcome the aforementioned obstacles. Our main contributions provide a positive answer to the stated question, summarized as follows.

• By leveraging the geometric properties of doubling metrics and incorporating local fairness information, we develop a candidate-based structural method that effectively reduces the gap between the initial clustering centers and the final feasible solution. Based on the proposed method, we obtain (1 + ε)-approximation algorithms for the GF-k-CEN and DSF-k-CEN problems in bounded doubling metrics, with FPT running time.

• The proposed candidate-based structural method induces a crucial distance-bounded property that states theoretically the existence of (1 + ε)-approximate solutions for the GF-k-CEN and DSF-k-CEN instances.

We summarize the comparison between our results and existing work in Table 1. Formally, our main theoretical guarantees are stated as follows.

Theorem 1. For a real number ε > 0, there exists a (1 + ε)- approximation algorithm of fairness violation by one for the GF-k-CEN problem in bounded doubling metrics with running time f(k, ε)nO(1) , where f(k, ε) = (kε-1 )O(k) .

Theorem 2. For a real number ε > 0, there exists a (1+ε)-approximation algorithm for the DSF-k-CEN problem in bounded doubling metrics with running time f(k, ε)nO(1) , where f(k, ε) = (kε-1 )O(k) .

1.2 Other RelatedWork

The doubling dimension (see Section 2 with a formal definition) captures the intrinsic dimensionality of a general metric space and can be viewed as a natural extension of the notion of dimensionality in Euclidean space. As noted in [Pellizzoni et al., 2025], in many real-world instances, the points of interest either lie in low-dimensional space or are supported on low-dimensional manifolds embedded in higher-dimensional metric space. Moreover, the structural properties of spaces with low doubling dimension have been exploited to design efficient clustering algorithms that achieve improved tradeoffs between computational resources and approximation quality compared to dimension-insensitive strategies [Ceccarello et al., 2017; Goranci et al., 2021].

For the k-center problem in doubling metrics, existing research has primarily focused on the construction of coreset [Aghamolaei and Ghodsi, 2018; Ding et al., 2019; Ceccarello et al., 2019], and the design of approximation algorithm on fully dynamic model [Goranci et al., 2021; Pellizzoni et al., 2025]. More broadly, a wide range of algorithmic strategies have been proposed for the k-median and k-means problems in bounded doubling metrics [Huang et al., 2018; Friggstad et al., 2019; Cohen-Addad, 2020; Cohen-Addad et al., 2021]. In contrast, the study of fair clustering in doubling metrics remains largely unexplored. With the exception of a few approximation algorithms developed in distributed settings [Wu et al., 2024; Ceccarello et al., 2024], there are no known sequential results for fair clustering in doubling metrics. This gap further motivates our investigation into fair clustering under geometric constraints.

2 Preliminaries

For any integer m ≥ 1, let [m] = {1, . . . ,m}. Let (X, d) be a metric space, and let C ⊆ X denote the set of points considered in this paper. For any point v ∈ C and an integer r ≥ 0, the ball centered at v with radius r is defined as B(v, r) = {c ∈ C | d(c, v) ≤ r}. For any point v ∈ C and a subset S ⊆ C, let d(v, S) = mins∈S d(v, s) denote the distance from v to its nearest center in S. In this paper, we mainly consider the metric space with bounded doubling dimension [Assouad, 1983; Gupta et al., 2003], which is widely considered in clustering problems [Huang et al., 2018; Ding et al., 2019; Cohen-Addad, 2020; Cohen-Addad et al., 2021; Ceccarello et al., 2024]. The doubling dimension of (X, d) is the smallest number, denoted as D, such that for any point v ∈ C and radius r, all points in the ball B(v, r) are always covered by the union of at most 2D balls with radius r/2.

Definition 1 (the k-center problem). An instance of the kcenter problem is denoted by ((X, d), C, k), where (X, d) is a metric space, C ⊆ X is a set of points, and k is a positive integer, respectively. The goal is to find a subset S ⊆ C of k centers such that the cost maxv∈C d(v, S) is minimized.

We now introduce the notions of fairness considered in this paper. Assume that the given data point C is divided m disjoint groups P = {C1, . . . ,Cm} such that ∪mh=1Ch = C, where each point in Ch (h ∈ [m]) is said to have color h. We call such P a partition of C.

Definition 2 (the GF-k-CEN problem). An instance of the GF-k-CEN problem is denoted by ((X , d), C, P, ⃗α, ⃗ β, m, k), where (X , d) is a metric space, C ⊆ X is a set of points with a partition P = {C1, . . . ,Cm}, ⃗α = (α1, . . . , αm), ⃗ β = (β1, . . . , βm) are two fairness vectors, and m, k are two positive integers, respectively. The goal is to find a subset S ⊆ C of k centers, and a mapping ϕ : C → S such that the cost maxv∈C d(v, ϕ(v)) is minimized, and ϕ satisfies the group fairness constraints, i.e., for any s ∈ S, h ∈ [m], αh ≤ |{v∈Ch|ϕ(v)=s}| |{v∈C|ϕ(v)=s}| ≤ βh.

Given an instance ((X , d), C, P, ⃗α, ⃗ β,m, k) of the GF-kCEN problem, a pair (S, ϕ) is called a feasible solution of this instance if S ⊆ C is a set with size k, and ϕ : C → S is a mapping satisfying group fairness constraints.

Definition 3 (the DSF-k-CEN problem). An instance of the DSF-k-CEN problem is denoted by ((X, d),C,P, ⃗ θ, m, k), where (X, d) is a metric space, C ⊆ X is a set of points with a partition P = {C1, . . . , Cm}, ⃗ θ = (k1, . . . , km) is a fairness vector satisfying ∑mh=1 kh = k, and m, k are two positive integers, respectively. The goal is to find a subset S ⊆ C of k centers such that the cost maxv∈C d(v, S) is minimized, and S satisfies the data summarization fairness constraints, i.e., for any h ∈ [m], |S ∩Ch| = kh.

Given an instance ((X, d),C,P, ⃗ θ,m, k) of the DSF-kCEN problem, S is called a feasible solution of this instance if S is a subset of C with size k satisfying data summarization fairness constraints. Throughout this paper, let τ and τf denote the costs of optimal solutions of the unconstrained kcenter instance and the corresponding GF-k-CEN (or DSF-kCEN) instance, respectively. Since the feasible solution of the GF-k-CEN (or DSF-k-CEN) instance is also feasible to the corresponding k-center instance, it follows that τ ≤ τf . Note that for the GF-k-CEN (or DSF-k-CEN) problem, the cost of optimal solution is always the distance between two points in C. Hence, the value of τf can be determined via a binary search over all pairwise distances, incurring an additional factor of O(n2 ) in the running time. In the subsequent analysis, we assume that τf is known for the given instance, which is a standard and widely used technique for the k-center problem and its variants [Khuller and Sussmann, 2000]. Let (S∗ , ϕ∗ ) denote an optimal solution to the GF-k-CEN (or DSF-k-CEN) instance with cost τf , where S∗ = {s∗1 , . . . , s∗k } is the set of k optimal centers, and ϕ∗ is the associated assignment function. Let O∗ = {O∗ 1 , . . . ,O∗ k } denote the set of k optimal clusters induced by ϕ∗ . Note that for the DSF-k-CEN problem, the assignment function ϕ∗ can be omitted.

3 An Overview of Our Algorithms

In this paper, we propose a candidate-based structural method for the GF-k-CEN and DSF-k-CEN problems in doubling metrics. Since the quality of a set of k initial clustering centers critically affects the finding of approximate solutions, our method begins by constructing a candidate set that contains a high-quality set of k initial clustering centers, leveraging the geometric properties of doubling metrics. Intuitively, the candidate construction process aims to build a representative subset of the given dataset such that it contains at least one point that approximately captures the location of optimal center. Compared with the bi-criteria solution given in [Goyal and Jaiswal, 2023], our method can effectively reduce the gap between the set of k initial clustering centers and the final feasible solution by working with the carefully designed candidate set. To further convert the set of initial clustering centers into a feasible solution without loss in approximation guarantee, our method explicitly exploits the local structural properties induced by fairness constraints itself. In particular, it establishes a distance-bounded property that enables the conversion while maintaining approximation quality. Specifically, this property theoretically states that there must exist a feasible solution with cost at most a factor (1 + ε) of the optimal solution cost, where ε is a parameter used to control the approximation ratio. Equivalently, we can achieve a small gap between the approximate solution obtained by the set of initial clustering centers and the optimal solution. In contrast, the method of [Goyal and Jaiswal, 2023] directly relies on linear programming and min-cost flow network to convert a bi-criteria solution into a feasible one, without explicitly considering the local structural properties. As a result, their method does not effectively control the approximation gap, and is difficult to extend to the DSF-k-CEN problem. Our method can overcome these limitations to obtain desired approximate solutions in FPT time by combining with problemspecific selection algorithms.

We now provide an intuitive overview of our parameterized algorithms for the GF-k-CEN and DSF-k-CEN problems in doubling metrics. Instead of directly selecting the set of k initial clustering centers, our algorithm first utilizes the structure of doubling metrics to reduce the input to a carefully chosen candidate set without imposing fairness constraints. In the resulting candidate set, we then identify the high-quality set of clustering centers by enumerating all possible subsets of size k. Finally, depending on the specific fairness requirement, we apply appropriate algorithmic techniques to obtain desired feasible solutions with minimum clustering cost. Specifically, we employ linear programming and min-cost flow network for the GF-k-CEN problem, while the maximum matching method is used for the DSF-k-CEN problem. By the above process, we develop FPT time (1 + ε)-approximation algorithms for the GF-k-CEN and DSF-k-CEN problems, respectively, where ε > 0 is a given parameter.

4 Parameterized Approximation Algorithms

We now present our parameterized approximation algorithms for the GF-k-CEN and DSF-k-CEN problems. For brevity, we use the GF-k-CEN problem as an example for the analysis, which can be easily adapted to the DSF-k-CEN problem. Consider an instance ((X , d), C, P, ⃗α, ⃗ β,m, k) of the GF-kCEN problem. By utilizing the geometric property of doubling metrics, we reduce the given data points to a candidate set of centers. Specifically, we consider the method in [Ceccarello et al., 2019] with the following result.

Theorem 3. Given an instance ((X , d), C, k) of the k-center problem with the bounded doubling dimension D and a real number ε > 0, we can obtain a subset E ⊆ C with size k · (4/ε)D in polynomial time such that for any v ∈ C, d(v,E) ≤ ετ, where τ is the optimal cost of this instance.

Note that Theorem 3 still holds for the GF-k-CEN problem instance due to τ ≤ τf . We now show that the candidate set E constains a high-quality set of initial clustering centers.

Lemma 1. There must exist a subset S ⊆ E with size k such that for any v ∈ C, d(v, S) ≤ (1 + ε)τf .

Proof. For any i ∈ [k], let π(s∗i ) = argminv∈E d(v, s∗i ) be the closest point in E to s∗i . Then, for any v ∈ O∗ i (i ∈ [k]), we have d(v, π(s∗i )) ≤ d(v, s∗i ) + d(s∗i , π(s∗i )) ≤ τf + ετ ≤ (1 + ε)τf , where the first inequality follows from the triangle inequality, and the last inequality holds due to τ ≤ τf and Theorem 3. Hence, there must exist a subset S = {π(s∗1 ), . . . , π(s∗k )} ⊆ E with size k such that for any v ∈ C, d(v, S) ≤ (1 + ε)τf .

Lemma 1 implies that there must exist a subset S of E that induces a (1 + ε)-approximation without satisfying fairness constraints by assigning each point of C to its closest center in S. Notably, S may be a multi-set, since it is possible that some optimal centers have the same closest point in E. Formally, we call such S a set of ε-optimal cluster centers (i.e., the high-quality set of initial clustering centers). Indeed, there are |E|k subsets with size k of E, and one of them induces a (1+ε)-approximation without satisfying fairness constraints. To determine which one is the set of ε-optimal cluster centers, a problem-specific selection algorithm (see [Ding and Xu, 2020] with more details) is needed to take each subset with size k of E as input, and output the subset with the minimum clustering cost. For simplicity, assume that we have found the set S of ε-optimal cluster centers for given instance. To convert the set of ε-optimal cluster centers obtained to one satisfying fairness constraints without approximation loss, in the following, we prove that for the GF-k-CEN problem, there must exist a (1+ε)-approximate solution (note that the solution satisfies fairness constraints).

Lemma 2. Given an instance ((X, d),C,P, ⃗α, ⃗ β,m, k) of the GF-k-CEN problem and a real number ε > 0, let S = {s1, . . . , sk} be the set of ε-optimal cluster centers of this instance. Then, there must exist a (1+ε)-approximate solution of this instance based on S.

Proof. For any i ∈ [k] and h ∈ [m], let O∗ i (h) denote the set of points in O∗ i with color h. Obviously, for any i ∈ [k], we have O∗ i = ∪h∈[m]O∗ i (h) . For any i ∈ [k], let π(s∗i ) = arg mins∈S d(s, s∗i ) denote the closest center in S to s∗i . By the definition of the set S of ε-optimal cluster centers, it follows that d(s∗i , π(s∗i )) ≤ ετf . For any point v ∈ C, let ϕ(v) = π(ϕ∗ (v)). We now claim that (S, ϕ) forms a (1 + ε)- approximate solution. For any point v ∈ O∗ i (i ∈ [k]), by the triangle inequality, we have d(v, ϕ(v)) = d(v, π(ϕ∗ (v))) ≤ d(v, ϕ∗ (v)) + d(ϕ∗ (v), π(ϕ∗ (v))) ≤ (1 + ε)τf . Hence, the cost of (S, ϕ) is at most (1 + ε)τf . We next verify the group fairness constraints. Since (S∗ , ϕ∗ ) is a feasible solution, for any i ∈ [k] and h ∈ [m], αh ≤ |O∗ i (h)|/|O∗ i | ≤ βh. For any s ∈ S, let N(s) = {s∗i ∈ S∗ | π(s∗i ) = s} denote all centers in S∗ such that s is the closest center. Observe that {v ∈ C | ϕ(v) = s} = ∪s∗i ∈N(s)O∗ i , and similarly, for any h ∈ [m], {v ∈ Ch | ϕ(v) = s} = ∪s∗i ∈N(s)O∗ i (h). Consequently, for any h ∈ [m] and s ∈ S, we have |{v∈Ch|ϕ(v)=s}| |{v∈C|ϕ(v)=s}| = ∑s∗i ∈N(s) |O∗ i (h)| ∑s∗i ∈N(s) |O∗ i | . Using a scaling technique, we have mins∗i ∈N(s) |O∗ i (h)| |O∗ i | ≤ ∑s∗i ∈N(s) |O∗ i (h)| ∑s∗i ∈N(s) |O∗ i | ≤ maxs∗i ∈N(s) |O∗ i (h)| |O∗ i | . Combining this with the feasibility of (S∗ , ϕ∗ ), we conclude that αh ≤ ∑s∗i ∈N(s) |O∗ i (h)| ∑s∗i ∈N(s) |O∗ i | ≤ βh,

which shows that ϕ satisfies group fairness constraints.

Lemma 2 implies a distance-bounded property: there must exist a mapping ϕ satisfying the group fairness constraints that assigns each point in C to a center in S within distance (1 + ε)τf . The remaining task is to find such a desired approximate solution by the distance-bounded property. In the following, we will show how to obtain the desired FPT approximation algorithms by combining the proposed method with problem-specific selection algorithms for each problem.

Algorithm 1: An algorithm for GF-k-CEN

Input: An instance ((X , d), C, P, ⃗α, ⃗ β,m, k) of the GF-k-CEN problem and parameters ε, τf

Output: A pair (S, ϕ)

1 Let E be the candidate set constructed by Theorem 3;

2 for each multi-set S ⊆ E do

3 x← solve the linear programming relaxation;

4 Construct a min-cost flow network G based on x;

5 x←find a min-cost flow on G;

6 ∀i ∈ S, j ∈ C : ϕ(j) ← i if xij > 0;

• 7 Output (S, ϕ) such that the cost of (S, ϕ) is minimized among all considered subsets;

8 return (S, ϕ).

4.1 The GF-k-CEN Problem

In this section, we consider the GF-k-CEN problem. Based on S, our algorithm starts with linear programming to get a fractional solution with cost at most (1 + ε)τf . In order to modify the fractional solution obtained, it constructs a mincost flow network to get an integral solution, which has the cost bounded by (1 + ε)τf , and violates the fairness constraints by one (see Algorithm 1). Formally, we start with the following linear programming.

min 1

Here the binary variable xij indicates whether point j ∈ C is assigned to center i ∈ S. Note that the value of xij represents the assignment ϕ. Constraint (1) ensures that each point j ∈ C is assigned to a center. Constraint (2) captures group fairness constraints. Indeed, constraint (4) is based on the distance-bounded property that ensures the cost of the fractional solution obtained is at most (1 + ε)τf . Since the intractableness of integral linear programming, we relax constraint (3) by allowing xij ∈ [0, 1] for all i ∈ S, j ∈ C, yielding a linear programming relaxation. Let x denote an optimal solution to the linear programming relaxations, which has the property that the assignment satisfies the group fairness constraints, but the points may be fractionally assigned to several centers in S. Let cost(x) denote the cost of the solution x. The remaining task is to obtain an integral solution x with cost(x) ≤ (1 + ε)τf . By constructing a min-cost flow network, we can obtain such an integral solution.

Lemma 3. Given an instance ((X, d),C,P, ⃗α, ⃗ β,m, k) of the GF-k-CEN problem and a real number ε > 0, let x be the solution returned by the linear programming relaxations. Then, we can obtain a (1 + ε)-approximate solution x with an additive 1 violation for group fairness constraints in FPT time based on a min-cost flow network.

Proof. For any i ∈ S, h ∈ [m], let T h i = ∑j∈Ch xij, Ti = ∑j∈C xij , Bi = ⌊Ti⌋-∑h∈[m] ⌊T h i ⌋,B = |C|-∑i∈S ⌊Ti⌋. We construct a min-cost flow network G = (V, A) with unit capacities and costs on the edges as well as demands on the nodes as follows: (1) V = V1 ∪ V2 ∪ V3 ∪ V4 ∪ V5, where V1 = {s} with demand |C|, V2 = {vj | j ∈ C} with demand 0, V3 = {vh i | i ∈ S, h ∈ H} with demand -⌊T h i ⌋, V4 = {vi | i ∈ S} with demand -Bi, and V5 = {t} with demand -B. (2) A = A1 ∪ A2 ∪ A3 ∪ A4, where A1 = {(s, vj) | j ∈ C} with cost 0, A2 = {(vj, vh i ) | j ∈ Ch, i ∈ S, h ∈ [m], xij > 0)} with cost d(i, j), A3 = {(vh i , vi) | i ∈ S, h ∈ [m], T h i - ⌊T h i ⌋ > 0} with cost 0, and A4 = {(vi, t) | i ∈ S, Ti - ⌊Ti⌋ > 0} with cost 0.

Observe that the sum of the demands over all nodes in V is equal to zero. Hence, the flow conservation holds. Moreover, all capacities, costs, and demands are integral. Consequently, the min-cost flow network G = (V,A) admits an integral optimal solution. Let f be an optimal flow. It naturally induces a solution x by setting xij equal to the flow value on edge (vj, vh i ) ∈ A2 for each j ∈ C and i ∈ S. Since the flow f is integral, this implies that x is integral. Furthermore, since xij > 0 only when d(i, j) ≤ (1 + ε)τf , we have cost(x) ≤ (1 + ε)τf .

We now show that the integral solution x incurs an additive 1 violation of the group fairness constraints. For each i ∈ S and h ∈ [m], the demands of nodes vh i and vi imply that at least ⌊T h i ⌋ points with color h and at least ⌊Ti⌋ points in total are assigned to center i. On the other hand, since the arcs (vh i , vi) and (vi, t) have unit capacity, and each node vh i and vi has at most one outgoing arc, at most ⌈T h i ⌉ points with color h and at most ⌈Ti⌉ points in total can be assigned to i. Therefore, we have ⌊T h i ⌋ ≤ ∑j∈Ch xij ≤ ⌈T h i ⌉ and ⌊Ti⌋ ≤ ∑j∈C xij ≤ ⌈Ti⌉. By the definition of violation in [Bercea et al., 2019], this implies that x satisfies the group fairness constraints with an additive 1 violation.

Finally, we analyze the running time. The time required to compute the candidate set E is polynomial by Theorem 3. We then enumerate all subsets of E of size k, compute the corresponding clustering, and output the subset with minimum cost. There are |E|k such subsets. Since the metric space has bounded doubling dimension D = O(1), we have |E|k = kk · (4/ε)Dk = (kε-1 )O(k) . For each subset of size k, solving the associated linear programming and min-cost flow network is polynomial. Thus, the overall running time is bounded by (kε-1 )O(k)nO(1) , which is FPT(k)-time.

Lemma 3 shows that the min-cost flow network yields a (1 + ε)-approximate solution with an additive 1 violation of the fairness constraints. Indeed, the violation can be removed using the mixed-integer linear programming of [Bandyapadhyay et al., 2021] that introduces additional variables to capture the number of points with each color assigned to the centers in S. In particular, one can obtain a (1 + ε)- approximate solution that satisfies the fairness constraints exactly in FPT(k,m)-time [Bandyapadhyay et al., 2021], incurring an additional dependence on the number of colors m in running time. Compared with the method of [Bandyapad-

Algorithm 2: An algorithm for DSF-k-CEN

Input: An instance ((X , d), C, P, ⃗ θ,m, k) of the DSF-k-CEN problem and parameters ε, τf

Output: A solution ˆ S

• 1 Let E be the candidate set constructed by Theorem 3;

2 for each multi-set S ⊆ E do

3 Construct a bipartite graph G based on S;

4 Obtain ˆ S by maximum matching method on G;

• 5 Output ˆ S such that the cost of ˆ S is minimized among all considered subsets;
• 6 return ˆ S.

hyay et al., 2021], our use of a min-cost flow network has polynomial running time, and is more efficient in practice. Combining these results completes the proof of Theorem 1.

4.2 The DSF-k-CEN Problem

In this section, we study the DSF-k-CEN problem, and employ the matching-based method of [Jones et al., 2020] to solve it. Specifically, by combining our candidate-based structural method with the matching algorithm, we obtain a (1+ε)-approximate solution without fairness violation for the DSF-k-CEN problem with running time (kε-1 )O(k)nO(1) . Given the set S of ε-optimal cluster centers, the algorithm computes a maximum matching based on the bipartite graph, which induces a set ˆ S of k centers satisfying data summarization fairness constraints (see Algorithm 2). Theorem 2 then follows from the result stated below.

Lemma 4. Given an instance ((X, d),C,P, ⃗ θ,m, k) of the DSF-k-CEN problem and a real number ε > 0, let S be the set of ε-optimal cluster centers. Then, we can obtain a (1 + ε′ )-approximate solution without fairness violation of this instance in FPT time, where ε′ = 2ε.

Proof. We first prove the existence of a (1+ε′ )-approximate solution for the given instance. Recall that the set S of εoptimal cluster centers satisfies the following property: for each optimal center s∗i ∈ S∗ (i ∈ [k]), there exists a center in S at distance at most ετf from s∗i . Consequently, for each si ∈ S (i ∈ [k]), there must exist a point, denoted by f(si), with the same color as s∗i (possibly s∗i itself) such that d(si, f(si)) ≤ ετf . Let F = {f(s1), . . . , f(sk)}. Then, for any point v ∈ O∗ i (i ∈ [k]), by the triangle inequality, we have that d(v, f(si)) ≤ d(v, si) + d(si, f(si)) ≤ (1 + ε)τf + ετf ≤ (1 + 2ε)τf . Thus, for each point v ∈ C, we have d(v, F ) ≤ (1 + 2ε)τf . Assigning each point in C to its closest center in F yields a feasible solution with cost at most (1 + 2ε)τf . Let ε′ = 2ε. Hence, there exists a (1 + ε′ )- approximate solution for the given instance.

We now show how the matching algorithm constructs such a desired solution. The algorithm starts with a bipartite graph G = (V1 ∪ V2, A). The left vertex set V1 contains k vertices in total, one vertex ui for each center si ∈ S (i ∈ [k]). The right vertex set is V2 = ∪mh=1Vh, where Vh contains exactly kh identical vertices corresponding to color h (h ∈ [m]). For each i ∈ [k] and h ∈ [m], if there is a point v ∈ Ch with d(v, si) ≤ ετf , then we connect ui to all vertices in Vh. Let M be the maximum matching returned by the Ford-Fulkerson algorithm based on G that runs in polynomial time. Then, M induces immediately a solution ˆ S as follows. For each matched edge (ui, b) ∈ M, assume that vertex b is in Vh. We select a point p ∈ Ch with d(p, si) ≤ ετf , and include p in ˆ S. By construction, for each center in S, there exists at least one such point matching the color of the corresponding optimal center in S∗ . Moreover, these balls centered at si (si ∈ S) with radius ετf are pairwise disjoint. Thus, the number of edges in maximum matching M is equal to k. Since |Vh| = kh, and M is a maximum matching, ˆ S contains exactly kh points with color h. Therefore, ˆ S satisfies data summarization fairness constraints. Then, by assigning each point v ∈ C to its closest center in ˆ S, we obtain a feasible solution ˆ S with cost (1+ε)τf . The running time analysis follows the same argument as in Lemma 3. Since the matching algorithm runs in polynomial time, the total running time is (kε-1 )O(k)nO(1) , which is FPT(k)-time.

5 Experiments

While the primary focus of this paper is on theoretical aspect, we use the GF-k-CEN problem problem as an illustrative example, and try to compare our proposed parameterized approximation algorithm with the state-of-the-art algorithms in this section. All linear programs are solved using CPLEX. The experiments are conducted on a machine equipped with 72 Intel Xeon Gold 6230 CPUs and 500GB of memory.

Datasets. We conduct experiments on 3 real datasets (i.e., Reuters, Victorian and 4area) frequently used in fair clustering [Harb and Lam, 2020]. Reuters dataset contains 50 English language texts from each of 50 authors, where author is considered as the sensitive attribute to generate 50 groups. Victorian dataset contains the texts from 45 English language authors, in which each text consists of 1000-word sequences obtained from a book of the author. We use author as sensitive attribute to get 45 groups. 4area dataset contains researchers from four areas of computer science, where the main area of research is considered as the sensitive attribute to generate 4 groups. We normalize all used datasets to have zero mean and standard deviation of one. The datasets used in our experiments are summarized in Table 2.

Baseline Algorithms. We use two baseline algorithms in our experiments. The first one is the classical greedy algorithm that is a 2-approximation for the k-center problem, denoted as GREEDY-kC. We compare the cost returned by GREEDYkC that is the maximum distance from a point to its closest center, and is also a lower bound of the optimal cost for the GF-k-CEN instance. Note that GREEDY-kC is not strictly a baseline algorithm, and it is included to provide a reference lower bound for evaluating the performance of fair clustering algorithm. The second one is a 3-approximation with additive violation 7 by [Harb and Lam, 2020], denoted as HARB. Indeed, we do not consider the algorithm in [Bercea et al., 2019] that achieves a 3-approximation with additive violation 1 (note that the definition of violation is different from one in [Harb and Lam, 2020]), since the algorithm in [Harb and Lam, 2020] has better performance.

Parameters and Results. Our parameterized algorithm begins by computing a candidate set of size k · (4/ε)D . However, the doubling dimension D is hard to compute in practice, and is thus not treated as an explicit parameter in experiments. Following the settings in [Ceccarello et al., 2019; Ceccarello et al., 2024; Wu et al., 2024], we instead vary the size of the candidate set directly. In our experiments, we fix the candidate set size to 3k. Tables 3 compares the average clustering costs achieved by different algorithms for the GF-k-CEN problem. In particular, for the GF-k-CEN problem, we choose feasible values of ⃗α, ⃗ β as in [Harb and Lam, 2020], and fix k = 3. As shown in Table 3, our parameterized algorithm consistently achieves lower clustering cost across a variety of datasets and parameter settings. Note that we do not include a comparison of running times in experiments. As expected, the running time of our parameterized algorithm is significantly higher than that of HARB, since our algorithm enumerate all possible subsets of candidate centers in order to obtain solutions with smaller clustering cost.

6 Conclusions

In this paper, we study the k-center problem under group fairness and data summarization fairness constraints in doubling metrics. Our proposed algorithms can be easily extended to the k-supplier variant, in which the set of selected centers is different from the set of data points. It is also interesting to extend our method to the setting where data points may belong to multiple demographic groups. More broadly, given the growing interest in theoretical foundations of fair clustering, we believe that the method developed in this paper will be applicable to a wide range of fairness-aware variants of the k-center problem.

Acknowledgments

This work was supported by the National Natural Science Foundation of China (Nos. 62432016, 62502545) and the Central South University Research Program of Advanced Interdisciplinary Studies (No. 2023QYJC023).