Parameterized Approximation Algorithm for Doubly Constrained Fair Clustering

1 Introduction

Clustering is a fundamental problem in machine learning, and has numerous applications in data mining, image classification, and beyond. Given a set of points in a metric space, the goal is to partition these points into several disjoint clusters such that points within the same cluster are close to each other, while points in different clusters remain relatively far apart. Several classic clustering models have been extensively studied, such as k-center, k-means [Huang et al., 2024], and k-median. In this paper, we focus on the k-median problem, in which we are given a set C of clients, a set F of facilities in a metric space (X, d), and a positive integer k. The goal of the metric k-median problem is to open a subset in F of k facilities such that the total distance from each client to its closest opened facility is minimized. The metric k-median problem is NP-hard, leading to a rich line of research on obtaining efficient approximation algorithms. The first constant-factor approximation algorithm for the metric k-median problem was given by [Charikar et al., 2002], which was improved to (3 + ϵ) by [Arya et al., 2004] using a local-search method [Huang et al., 2023]. Currently, the best known approximation factor for the metric k-median problem is 2.675 [Byrka et al., 2017] by the dependent rounding technique, and the problem is known to be NP-hard to approximate to a factor less than 1 + 2/e [Guha and Khuller, 1998]. Moreover, finding an optimal solution for the metric k-median problem is known to be W[2]-hard if parameterized by k due to a reduction by [Guha and Khuller, 1998] (nO(1) g(k) time for an input size of n and a positive function g, denoted by FPT(k)-time for brevity). Recently, [CohenAddad et al., 2019] presented approximation algorithm in FPT(k)-time with ratio (1+2/e+ϵ) for the metric k-median problem, which is essentially tight assuming the Gap-ETH.

∗Corresponding author

Recently, fair clustering has been extensively studied, and lots of definitions about fairness have been proposed, such as group fairness [Ahmadian et al., 2019; Bera et al., 2019; Bercea et al., 2019; Harb and Lam, 2020], data summarization fairness [Chiplunkar et al., 2020; Jones et al.

Kleindessner et al., 2019; Angelidakis et al., 2022; Zhang et al., 2024b], proportional fairness [Chen et al., 2019; Micha and Shah, 2020], individual fairness [Mahabadi and Vakilian, 2020; Negahbani and Chakrabarty, 2021], etc. Despite these notions being well-justified, they are often examined independently. Motivated by the fact that many clustering applications require a unified solution that simultaneously satisfies multiple fairness notions, [Dickerson et al., 2023] introduced the doubly constrained fair clustering that integrates both group fairness and data summarization fairness. Both fairness notions are motivated by the principle of disparate impact [Feldman et al., 2015], which asserts that different groups should receive equitable treatment, making the intersection of both notions a natural consideration. As noted in [Dickerson et al., 2023], combining group fairness and data summarization fairness is particularly relevant, since both focus on demographic fairness and the representation of groups. Furthermore, the incompatibility is studies between the above two fairness constraints and a family of other fairness constraints. In this paper, following the prior work, we focus on the doubly constrained fair clustering. More precisely, we consider the doubly constrained fair clustering under the k-median objective, referred to Doubly Constrained Fair k-Median (DF-k-MED). In the doubly constrained fair clustering instance, we are given a set of facilities and a set of clients in a metric space, where both facilities and clients are divided into several disjoint groups, and each facility or client is assigned a color to denote which group it is in. The goal is to form k clusters such that the clustering objective is minimized, while ensuring that the proportion of clients of each color in every cluster is within a specified range, and that the number of opened facilities of each color is equal to a given value.

[Chierichetti et al., 2017] introduced the definition of fairness involving only two colors, requiring that the proportion of both colors has approximately equal representation in every cluster. [Bercea et al., 2019] proposed the notion of group fairness, and provided a 4.675-approximation for the k-median objective, with an additive 1 violation for the group fairness constraints using linear programming and mincost flow network. The violation value represents the extent to which the fairness constraints are violated (see [Bercea et al., 2019] with details). [Ahmadian et al., 2019] studied the group fairness under the k-center objective with only an upper bound constraint, and presented a 3-approximation with an additive 2 violation, where the definition of violation differs from that in [Bercea et al., 2019], using linear programming and min-cost flow network. For the group fairness under the condition that colors are allowed to overlap, [Bera et al., 2019] developed a (ρ + 2)-approximation algorithm with (4∆+3) violation, where ρ is the factor given by any approximation algorithm for the k-median problem, and ∆ is the maximum number of colors a single point can belong to, respectively. Regarding parameterized result, [Bandyapadhyay et al., 2024] employed the fair coreset technique, and proposed a (3 + ϵ)-approximation for the group k-median problem, respectively, in FPT(k,m)-time where m is the number of client colors.

[Kleindessner et al., 2019] considered the data summarization fairness, and gave a constant-factor approximation algorithm in linear-time based on a swap technique for the kcenter objective. This approximation was subsequently improved to 3 by [Jones et al., 2020] through the maximum matching method, matching the approximation ratio of the matroid center problem [Chen et al., 2016] that generalize the data summarization fairness for the k-center objective. For data summarization under the k-median objective, which can be generalized to the matroid median problem [Krishnaswamy et al., 2011], the best known approximation ratio is (7.081 + ϵ) due to [Krishnaswamy et al., 2018]. [Thejaswi et al., 2022] extended data summarization fairness by introducing an additional lower-bound constraint on the number of selected facilities, and provided a (1+2/e+ϵ)-approximation for the k-median objective, running in FPT(k, t)-time, where t denotes the number of facility colors. Furthermore, [Zhang et al., 2024a] proposed (1 + ϵ)-approximation algorithm for the k-median objective in Euclidean metrics, operating in FPT(k, t)-time.

[Dickerson et al., 2023] considered the doubly constrained fair clustering for the k-center objective, and the method is not workable for the DF-k-MED problem due to different optimization objective. The previous parameterized algorithms in [Bandyapadhyay et al., 2024; Zhang et al., 2024a; Thejaswi et al., 2022] mainly enumerate feasible facilities based on their colors or construct coreset satisfying fairness constraints. However, these results are parameterized by both the number of opened facilities and the number of colors. The reason behind is that the related color information of fairness notions is essential for satisfying the group fairness or data summarization fairness. Therefore, in doubly constrained fair clustering, it seems inevitable that the approximation results have parameterized dependency on the number of colors. Moreover, due to the existence of two fairness constraints, the problem is considerably more challenging than its nonfair or one-fair counterpart. Since even if a set of k facilities is provided, it remains NP-hard to find a solution satisfying the group fairness constraints [Esmaeili et al., 2021]. Therefore, we must strategically ensure that the resulting solution satisfies both requirements while maintaining good approximation guarantees. Naturally, for the DF-k-MED problem, we then ask whether effective approximation algorithm can be developed in FPT(k)-time.

1.1 Our Contributions

In this paper, we propose a color-agnostic structural method to overcome the aforementioned obstacles. Our main contribution provides a positive answer to the stated question, summarized as follows.

• By exploring the local fairness information, we propose a color-agnostic structural method, which directly avoids the enumeration of clients or facilities with different colors, and exploits the inherent structures associated with fairness notions itself. Based on the proposed method, we obtain constant-factor approximation result for the DF-k-MED problem in FPT(k)-time, parameterized solely by the number of opened facilities.
• The proposed color-agnostic structural method simultaneously handles both fairness constraints while maintaining good approximation guarantees. Specifically, we theoretically prove that there must exist a (4 + ϵ)- approximation for the DF-k-MED problem, running in FPT time.

We summarize the results in the literature and ours in Table 1. Formally, we have following result for the DF-k-MED problem.

Theorem1. For any ϵ > 0, there exists a randomized (4+ϵ)- approximation algorithm of fairness violation by one for the DF-k-MED problem with running time f(k, ϵ)nO(1) , where f(k, ϵ) = (O(ϵ-2k log k))k .

2 Preliminaries

For any m ∈ Z+, let [m] = {1, . . . , m}. Given a metric space (X, d), let F ⊆ X and C ⊆ X denote the set of facilities and clients considered in this paper, respectively. Let |F∪C| = n. Given a client c ∈ C and a subset H ⊆ F, let d(c,H) = minf∈H d(c, f) be the distance from c to its nearest facility in H.

Definition 2 (the metric k-median problem). An instance of the k-median problem is denoted by ((X , d), F, C, k), where (X, d) is a metric space, F ⊆ X is a set of facilities, C ⊆ X is a set of clients, and k is a positive integer, respectively. The goal is to find a subset H ⊆ F of k facilities such that the cost ∑v∈C d(c, H) is minimized.

The coreset is a commonly used tool in clustering algorithms [Har-Peled and Mazumdar, 2004], defined formally as follows.

Definition 3 (coreset). Given an instance ((X, d),F, C, k) of the metric k-median problem and a parameter η > 0, a coreset is a subset of clients C † ⊆ C with associated weights {w(c) : c ∈ C † } such that for any subset of facilities H ⊆ F of size k, ∑c∈C† w(c)d(c, H) ∈ [1-η, 1+η] ·∑c∈C d(c, H).

The metric k-means problem has a similar definition of the coreset. [Chen, 2009] introduced the first coreset for the metric k-median problem, and the following result is the best known construction.

Theorem 4 ([Feldman and Langberg, 2011]). Given an instance ((X , d), F, C, k) of the metric k-median problem and parameters η > 0, γ < 1/2, there exists a randomized algorithm that, with probability at least (1 - γ), computes a coreset C † ⊆ C of size |C † | = O(η-2 (k logn + log 1 γ )) in time O(k(n+k) + log2 1 γ log2 1n ).

Theorem 4 implies that the original client set C can be reduced such that the total distance to any chosen facility set is distorted by at most a factor of (1 + η).

Definition 5 (the DF-k-MED problem). An instance of the doubly constrained fair k-median problem is denoted by ((X , d), F, P1, C, P2, ⃗ θ, ⃗α, ⃗ β, t, m, k), where (X , d) is a metric space, F ⊆ X is a set of facilities with a partition P1 = {F1, . . . ,Ft} satisfying ∪th=1Fh = F, C ⊆ X is a set of clients with a partition P2 = {C1, . . . , Cm} satisfying ∪mh=1Ch = C, ⃗ θ = (k1, . . . , kt) satisfying ∑th=1 kh = k, ⃗α = (α1, . . . , αm), ⃗ β = (β1, . . . , βm) are three fairness vectors, and t,m, k are three positive integers, respectively. The goal is to find a subset H ⊆ F of k facilities and a mapping φ : C → H such that the cost ∑v∈C d(c, φ(v)) is minimized, and the following conditions hold: (1) The set H satisfies the data summarization fairness constraints, i.e., for any h ∈ [t], |H ∩ Fh| ≤ kh; (2) The mapping φ satisfies the group fairness constraints, i.e., for any f ∈ H, h ∈ [m], βh ≤ |{c∈Ch|φ(c)=f}| |{c∈C|φ(c)=f}| ≤ αh.

Given an instance ((X, d),F,P1, C,P2, ⃗ θ, ⃗α, ⃗ β, t, m, k) the DF-k-MED problem, a pair (H, φ) is called a feasible solution of this instance if H ⊆ F is a set with size k satisfying data summarization fairness constraints, and φ : C → H is a mapping satisfying group fairness constraints. Let (H∗ , φ∗ ) be an optimal solution with cost opt = ∑c∈C d(c, φ∗ (c)), and let O∗ 1 , . . . ,O∗ k be the corresponding k optimal clusters under mapping φ∗ with C = ∪i∈[k]O∗ i . For any i ∈ [k] and h ∈ [m], let O∗ i (h) be the set of clients in O∗ i with color h. Then, we have O∗ i = ∪h∈[m]O∗ i (h).

3 An Overview of Our Algorithms

In this paper, we propose a color-agnostic structural method for the DF-k-MED problem based on the parameterized approximation framework developed by [Cohen-Addad et al., 2019]. This framework first identifies a set of clients, called leaders, which are close to the facilities opened by an optimal solution. It then selects the facilities to open by searching within annular regions centered on these leaders, where the radius of each region approximates the distance between the leader and its associated facility. Over the past few years, this framework has yielded various approximation algorithms in FPT time for clustering problem [Cohen-Addad and Li, 2019; Bandyapadhyay et al., 2024; Zhang et al., 2024a; Thejaswi et al., 2022], including capacitated clustering, fair clustering, etc. In the context of fair clustering, due to the existence of fairness constraints, it seems unavoidable that the parameterized approximation results include the parameter with respect to the number of colors. For instance, [Thejaswi et al., 2022] enumerated the set of facilities with different colors to satisfy the data summarization fairness constraints, while [Bandyapadhyay et al., 2024] constructed a composable coreset for group fairness through separately sampling on clients with different colors, resulting in the parameterized dependency on the number of colors to facilities or clients. Instead of enumerating feasible facilities or applying fair coreset techniques, both of which depend on the number of colors, our improved strategy avoids color-based parameters by adding an additional partition matroid constraint on the selected facilities and enumerating clients without considering their colors, based on the inherent structural properties exploited from fairness constraints itself.

We now provide an intuitive overview of our algorithm for the DF-k-MED problem. The algorithm begins by utilizing a coreset technique for the k-median problem to reduce the number of clients to a weighted set, without considering fairness constraints, as incorporating fairness into the coreset will incur parameter dependence on the number of colors [Bandyapadhyay et al., 2024]. In the resulting weighted set, our algorithm then identifies a set of leaders closed to the facilities in an optimal solution. By guessing the leaders and their distances to these facilities, the algorithm enumerates potential configurations of facilities within suitable distance ranges. Next, it constructs a monotone submodular function by introducing fictitious facilities, and solves a monotone submodular maximization problem under two partition matroid constraints, thus ensuring data summarization fairness. Finally, a weighted fair assignment problem is defined to assign the weighted clients to the chosen facilities satisfying the group fairness constraints, where a widely used linear programming procedure guarantees the desired approximation ratio. By the above process, we develop an FPT(k)-time approximation algorithm with approximation ratio (4 + ϵ) of 1 fairness violation for the DF-k-MED problem, where ϵ > 0 is a given parameter.

4 Parameterized Algorithm for Doubly Constrained Fair Clustering

We now present our color-agnostic structural algorithm for the DF-k-MED problem. The high-level idea of our algorithm is as follows. Consider an instance ((X, d),F,P1, C,P2, ⃗ θ, ⃗α, ⃗ β, t,m, k) of the DF-kMED problem and parameters η, γ, δ > 0. Let (H∗ , φ∗ ) be an optimal solution, where H∗ = {f ∗ 1 , . . . , f ∗ k } is the set of k facilities opened by the optimal solution. Our algorithm consists of two phases. The first phase (steps 1-15 of Algorithm 1) starts with the coreset technique on the instance with parameter η, yielding a weighted set C † of size O(η-2k log n) and an associated weight function w. Now our goal is to identify a subset H ⊆ F satisfying the data summarization fairness and a weighted assignment ψ from the clients in C † to H, minimizing the corresponding cost. Note that the first phase only focuses on the finding of H. Next we guess a set of leaders and distances between the leaders and the corresponding facilities. For any i ∈ [k], let ℓi be the closest client in C † to f ∗ i ∈ H∗ . We call ℓi the leader of f ∗ i . Let λi be the distance d(ℓi, f ∗ i ), rounded down to the closest integer power of (1 + δ) with parameter δ. The algorithm then enters an enumeration phase, with |C † |k choices for {ℓ1, . . . , ℓk} and O(δ-1 log n)k choices for {λ1, . . . , λk} (see Subsection 4.1 with more details). By enumerating over all |C † |kO(δ-1 log n)k combinations, we can assume that we have identified the correct leaders and distances. For each leader ℓi (i ∈ [k]), let Ni denote the set of facilities f ∈ F satisfying λi ≤ d(f, f ∗ i ) < (1 + δ)λi. To construct a monotone submodular function, we add a fictitious facility f ′ i to each Ni (i ∈ [k]). For any H ⊆ F, we then formulate a monotone submodular maximization problem under two partition matroid constraints to achieve the desired set H that satisfies data summarization constraints. The second phase

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;
• 2 Let dmin and dmax be the maximum and minimum distances between any two points in F ∪ C, respectively;
• 15 Output H such that Φ(C † , H) is minimized among all H computed in Line 14;
• 16 ψ ← solve the Weighted Assignment problem on C † and H;
• 17 φ ← obtain the assignment from the original client set C to H based on ψ;

3 Λ ← {dmin, (1 + δ)dmin, (1 + δ)2dmin, . . . , dmax}; 4 for each multi-set {ℓ1, . . . , ℓk} ⊆ C † do 5 for each multi-set {λ1, . . . , λk} ⊆ Λ do 6 for i = 1 to k do 7 Ni ← {f ∈ F | λi ≤ d(f, ℓi) < (1 + δ)λi}; 8 Construct a new facility f ′ i , and add it to Ni; for each f ∈ Ni do 9 d(f, f ′ i ) ← 2λi; 10 for each c /∈ Ni do 11 d(c, f ′ i ) ← minf∈Ni (d(c, f ) + d(f, f ′ i )); 12 F ′ ← {f ′1 , . . . , f ′k }; 13 Define ∆(H) = Φ(C † , F ′ ) - Φ(C † , H ∪ F ′ ) for any H ⊆ F ; 14 Find H ⊆ F maximizing function ∆(H) such that |H∩Ni| = 1 for any i ∈ [k], and |H ∩ Fi| = kh for any h ∈ [t];

18 return (H, φ).

(steps 16-17 of Algorithm 1) aims to find an assignment of clients from C † to the facilities in H satisfying the group fairness constraints. This phase avoids the use of fair coreset. To this end, we define a weighted assignment problem, and prove theoretical that there must exist a (4 + ϵ)-approximate solution for the DF-k-MED problem. For obtaining such solutions, we model the defined problem to the linear programming procedure, and utilize the min-cost flow network to solve it. Algorithm 1 details the specific process of our parameterized algorithm for the DF-k-MED problem.

4.1 Finding Feasible Facilities

In this section, we describe how to select a set H of k facilities that satisfies the data summarization fairness constraints in the first phase. The previous method in [Thejaswi et al., 2022] enumerated the feasible facilities with different colors, leading to the result parameterized by the number of colors to facilities. To avoid the enumeration, we explore the inherent structure related to the data summarization fairness constraints, and model it to a partition matroid constraint.

Consider an instance ((X , d), F, P1, C, P2, ⃗ θ, ⃗α, ⃗ β, t, m, k) of the DF-k-MED problem and a parameter η > 0. By applying a coreset construction with parameter η, we reduce the original client set C to a weighted set C † of size O(η-2k logn), where each client in C † is weighted by an integer indicating how many original clients it represents. However, the above process does not consider the inherent structural information of the clients, such as their colors, leading to a loss of the crucial attribute. Therefore, to address the later group fairness constraints, we record the number of points with each color assigned to each weighted client in C † . Specifically, consider a client c ∈ C † with weight w(c), and for any h ∈ [m], let nch denote the number of clients with color h assigned to c. Consequently, ∑mh=1 nch = w(c). Moreover, we introduce a function ρ : C → C † denoting the mapping relation. By applying Theorem 4, we can obtain a weighted instance ((X , d), F, P1, C † , w, P2, ⃗ θ, ⃗α, ⃗ β, t, m, k). For simplicity, we do not explicitly track the number of clients in the original set with different color assigned to the client in this weighted instance.

Recall that the goal of this section is to find a set H of facilities satisfying the data summarization fairness constraints. Let H∗ = {f ∗ 1 , . . . , f ∗ k } denote the set of k facilities opened by an optimal solution. For each f ∗ i ∈ H∗ (i ∈ [k]), let ℓi be the closest client in C † from f ∗ i . Assume that we have correctly guessed the set of k leaders (i.e., {ℓ1, . . . , ℓk}) with respect to the k optimal facilities. We now discuss how to guess the distance between f ∗ i and ℓi for any i ∈ [k]. Although the optimal facility f ∗ i is unclear, it is known that d(f ∗ i , ℓi) must be the distance between some facility and client in C ∪ F. Thus, we can use the following discretization trick. Let dmin and dmax be the minimum distance and the maximum distance of any two points in X, respectively. Then, the aspect ratio of this metric is dmax dmin , capturing the ratio of the largest to smallest pairwise distance among points in C ∪ F. It is well-known that we can assume that the aspect ratio can be bounded by polynomial in n [Cohen-Addad et al., 2019]. For a small parameter δ > 0, we can guess the distance d(f ∗ i , ℓi) from the set {dmin, (1 + δ)dmin, (1 + δ)2dmin, . . . , dmax}, which has at most log1+δ dmax dmin = O(logn) possible values. Assume that we have guess d(f ∗ i , ℓi) ∈ [λi, (1+δ)λi) where λi = (1 + δ)j dmin for some j ∈ [O(logn)]. Similarly, we can guess the discretized distances, denoted by λ1, . . . , λk, from each leader to its corresponding facility. Therefore, by enumerating over |C † |k (O(log n))k choices, we can guess the right ℓi and λi for all i ∈ [k].

For each leader ℓi (i ∈ [k]), we construct a facility set Ni = {f ∈ F | λi ≤ d(f, ℓi) < (1 + δ)λi}. Then, if we pick one arbitrary facility from each Fi, a good distancebased property will be obtained with respect to an optimal pick. However, the resulting set by this way fails to satisfy the data summarization fairness constraints, and incurs a large loss in approximation guarantee. To achieve a better approximation while satisfying fairness constraints, we first construct a monotone submodular function, and then invoke the monotone submodular maximization problem under two partition matroid constraints, capturing the data summarization fairness constraints. We now show how to construct a monotone submodular function. For each set Ni (i ∈ [k]), we introduce a new facility f ′ i , and add it to Ni. Further, for each f ∈ Ni, we set d(f, f ′ i ) = 2λi. For each client c ∈ C † , we define d(c, f ′ i ) = minf∈Ni (d(c, f ) + d(f, f ′ i )). Let F ′ = {f ′1 , . . . , f ′k } be the set of k new facilities. For any A ⊆ X, let Φ(C † ,A) = ∑c∈C† w(c)d(c,A). For any set H ⊆ F, we define the improvement function ∆(H) = Φ(C † ,F ′ ) - Φ(C † ,H ∪ F ′ ), and prove that it is monotone and submodular.

Lemma 6. For any H ⊆ F, the above defined function ∆(H) is monotone and submodular with ∆(∅) = 0.

Proof. It is easy to see that ∆(∅) = 0 by definition. We first show the function ∆(H) is monotone. Consider subsets H ⊆ H′ ⊆ F. We need to prove that ∆(H) ≤ ∆(H′ ). Then, we have Φ(C † ,F ′ ∪ H) = ∑c∈C† d(c,F ′ ∪ H) ≥ ∑c∈C† d(c,F ′ ∪ H′ ) = Φ(C † ,F ′ ∪ H′ ). Thus, we have ∆(H) ≤ ∆(H′ ).

We now need to prove that the function ∆(H) is monotone and submodular. Consider subsets H ⊆ H′ ⊆ F and facility f ∈ F. For each client c ∈ C † , we have x -min(x, y) = max(0, x - y), for any real numbers x and y. Then, we have

Thus, we have

which proves that the function is submodular.

We apply the approximation algorithm of [Lee et al., 2009] for monotone submodular maximization under multiple matroid constraints. We are interested in the set H that consists of one center from each Fi while satisfying the data summarization constraints, since one such set is the desired H∗ . Here, we aims to maximize ∆(H) under two partition matroid constraints, where the first one requires containing exactly one facility from each set Ni, and the second one asks for including at most kh facility from each set Fh. Note that the latter one captures the data summarization fairness constraints. Let H be the output in step 15 of Algorithm 1. By the result in [Lee et al., 2009], we have ∆(H) ≤ 1/2∆(H∗ ).

Lemma 7. Consider an instance I of the DF-k-MED problem with parameters η, γ, δ > 0. Let C † and H = {f1, . . . , fk} be the output in step 1 and step 15 of Algorithm 1, respectively. Then, for any parameter ϵ1 > 0, we have Φ(C † , H) ≤ (2 + ϵ1)opt, where opt is the optimal cost of I.

Proof. Let F ′ = {f ′1 , . . . , f ′k }. We first bound the cost induced by the set that opens facilities in F ′ . Consider a client c ∈ C † with d(c,H) = d(c, fi). Observe that since ℓi is the closest client from f ∗ i , we have d(c, f ∗ i ) ≥ d(ℓi, f ∗ i ) ≥ λi/(1 + δ). Thus, by the triangle inequality and the definition of facility f ′ i , we have d(c, f ′ i ) ≤ d(c, f ∗ i ) + d(f ∗ i , f ′ i ) = d(c, f ∗ i ) + 2λi ≤ d(c, f ∗ i ) +2(1+ δ)d(c, f ∗ i ) ≤ (3 + 2δ)d(c, f ∗ i ). Further, d(c,F ′ ) ≤ (3 + 2δ)d(c,H∗ ). Combing over all client c ∈ C † , ∑c∈C† w(c)d(c,F ′ ) = (3+2δ) ∑c∈C† w(c)d(c, H∗ ), and thus we have Φ(C † , F ′ ) ≤ (3 + 2δ)Φ(C † , H∗ ).

We next show that the set F ′ will not decrease the cost. Consider a client c ∈ C † with d(c, H) = d(c, fi), i.e., fi is the closest facility in H to c. Let σ(c) ∈ Ni be the closest facility to c in Ni. We claim that client c is closer to fi ∈ H than to f ′ i ∈ F ′ . Then, we have d(c, fi) ≤ d(c, σ(c))+d(σ(c), ℓi)+ d(ℓi, fi) ≤ d(c, σ(c))+λi +λi = d(c, σ(c))+d(σ(c), f ′ i ) = d(c, f ′ i ), where the first inequality follows from the triangle inequality, and the second inequality and the second equality use the definition of leader ℓi and facility f ′ i , respectively. Thus, d(c,H) ≤ d(c,F ′ ). Summing over all clients in C † , we obtain ∑c∈C† w(c)d(c, H) = ∑c∈C† w(c)d(c, H ∪ F ′ ). Thus, we have

By Definition 3 and the fact that the cost induced by H∗ is no more than that of (H∗ , φ∗ ), we get Φ(C † ,H∗ ) ≤ (1 + η)Φ(C,H∗ ) ≤ (1 + η)opt. Thus, Φ(C † ,H) ≤ (2 + ϵ1)opt with ϵ1 = O(ηδ).

4.2 Solving theWeighted Assignment Problem

Recall that a set H satisfying the data summarization fairness constraints is obtained in previous section. The goal of this section is to find an assignment from the weighted client set C † to the facilities in H, where the assignment satisfies the group fairness. To proceed, we modify the weighted instance ((X, d),F,P1, C † ,w,P † 2 , ⃗ θ, ⃗α, ⃗ β, t,m, k), since some structural information is not considered in the process of constructing coreset. Recall that for each client c ∈ C † , we record how many points with each color assigned to c, denoted as nc1 , . . . , ncm. Then, we have ∑mh=1 nch = w(c). For each client c ∈ C † , we divide c into m clients c1 , . . . , cm, where each client ch (h ∈ [m]) with the same position as c is assigned a weight nch with color h. Let C ‡ denote the new constructed set with the corresponding weight function w† : C ‡ → Z+ ∪ {0}. Therefore, the above problem can be defined as the following weighted assignment problem formally.

Definition 8 (the Weighted Assignment problem). Given a weighted set C ‡ of clients in a metric space (X, d) associated with weight function w† : C ‡ → Z+ ∪ {0}, a set P ‡ 2 = {C ‡ 1 , . . . , C ‡m} of m disjoint groups with ∪mh=1C ‡h = C ‡ , two fairness vectors ⃗α = (α1, . . . , αm), ⃗ β = (β1, . . . , βm), and a set H of k facilities, the goal is to find a mapping ψ : (C ‡ ×H) → Z+ ∪{0} satisfying ∑f∈H ψ(c, f ) = w† (c) for any c ∈ C ‡ , and the weighted group fairness constraints: for any f ∈ H, h ∈ [m], βh ≤ ∑c∈C‡h ψ(c,f ) ∑c∈C‡ ψ(c,f) ≤ αh, such that the cost ∑c∈C‡ ∑f∈H ψ(c, f )d(c, f ) is minimized.

Given an instance J = ((X, d), C ‡ ,w† ,P ‡ 2 , ⃗α, ⃗ β,H) of the Weighted Assignment problem, we call ψ a feasible solution of J if ψ satisfies weighted group fairness constraints and ∑f∈H ψ(c, f) = w† (c) for any c ∈ C ‡ . We define the cost of ψ as cost(ψ) = ∑c∈C‡ ∑f∈H ψ(c, f)d(c, f), which is the sum of the product of ψ(c, f) and distance between a client c ∈ C ‡ and a facility f ∈ H. Note that for any c ∈ C ‡ , f ∈ H, if ψ(c, f) > 0, the ψ(c, f) unit of weight of the client c is assigned to f. Let ψ∗ : (C ‡ × H) → Z+ ∪ {0} denote the optimal solution of J such that the cost ∑c∈C‡ ∑f∈H ψ∗ (c, f )d(c, f ) is minimized.

Lemma 9. Given an instance I of the DF-k-MED problem and parameters η, γ, δ > 0, let J be the obtained weighted assignment problem instance. Then, there must exist a solution ψ satisfying weighted group fairness constraints such that the cost of ψ is at most (4 + ϵ) times the optimal cost of I, where ϵ = O(ηδ).

Proof. Our proof strategy begins by constructing a mapping φ from the original client set C to the facility set H, which is then converted into the weighted mapping ψ : C ‡ → H. In this process, each client is assigned to the facility in H closest to its corresponding optimal facility. Since the optimal solution is feasible, we can ensure that the constructed mapping satisfies the weighted group fairness constraints. Moreover, by using the triangle inequality, we can bound the cost of the resulting assignment, thus obtaining the stated approximation guarantees.

We first show how to construct the mapping ψ. For any f ∗ i ∈ H∗ (i ∈ [k]), let π(f ∗ i ) = argminf∈H d(f, f ∗ i ) denote the closest facility in H to f ∗ i . For any c ∈ C, let φ(c) = π(φ∗ (c)). Note that the mapping φ is for the original client set C, and we need convert it to the weighted client set C ‡ to obtain ψ. For any client c ∈ C, assume that c is assigned to ch in C ‡ . By the definition of mapping ρ, we get that ρ(c) is the closest client in C † to c. Recall that for each color h ∈ [m], the weighted set C ‡ contains a client ch with the same position as ρ(c) ∈ C † . Thus, we have d(ch , c) = d(ρ(c), c) For any c ∈ C, if client c is assigned to the facility φ(c) ∈ H by φ, we assign 1 unit of weight of the client ch to φ(c), i.e., set ψ(ch , φ(c)) = 1. By the triangle inequality, we have d(ch , φ(c)) ≤ d(ch , c)+d(c, φ(c)) = d(ρ(c), c) + d(c, φ(c)). Consider a client c ∈ O∗ i (i ∈ [k]), and let f be the closest facility in H to the client ρ(c) in C ‡ that c is assigned. By the triangle inequality, we have d(c, φ(c)) ≤ d(c, f ∗ i )+d(f ∗ i , φ(c)) ≤ d(c, f ∗ i )+d(f ∗ i , f) ≤ d(c, f ∗ i ) + d(c, f ∗ i ) + d(c, f) ≤ 2d(c, f ∗ i ) + d(c, ρ(c)) + d(ρ(c), f), where the second inequality follows from that φ(c) is the closest facility in H to f ∗ i . Thus, we have that d(ch , φ(c)) ≤ 2d(c, f ∗ i ) + 2d(c, ρ(c)) + d(ρ(c), f). Combing over all client c ∈ C, we can get that cost(ψ) ≤ 2opt + 2ηopt + (2 + ϵ1)opt = (4 + ϵ1 + 2η)opt. Hence, the cost of ψ is at most (4 + ϵ)opt, where ϵ = O(ηδ).

The remaining task is to prove that ψ satisfies the weighted group fairness constraints. We first prove that the mapping φ on the original client set C satisfies the group fairness constraints. Since (H∗ , φ∗ ) is a feasible solution of I, for any i ∈ [k] and h ∈ [m], we have βh ≤ |O∗ i (h)| |O∗ i | ≤ αh. For any f ∈ H, let N(f) = {f ∗ i ∈ H∗ | π(f ∗ i ) = f} denote all facilities in H∗ such that f is the closest center. Note that {c ∈ C | φ(c) = f} = ∪f ∗ i ∈N(f)O∗ i . Similarly, for any h ∈ [m], we have {c ∈ Ch | φ(c) = f} = ∪f ∗ i ∈N(f)O∗ i (h). Consequently, for any f ∈ H and h ∈ [m], we get that |{c∈Ch|φ(c)=f}| |{c∈C|φ(c)=f}| = ∑f∗ i ∈N(f) |O∗ i (h)| ∑f∗ i ∈N(f) |O∗ i | . By using the scaling technique, we have that minf ∗ i ∈N(f) |O∗ i (h)| |O∗ i | ≤ ∑f∗ i ∈N(f) |O∗ i (h)| ∑f∗ i ∈N(f) |O∗ i | ≤ maxf ∗ i ∈N(f) |O∗ i (h)| |O∗ i | . Then, we get that βh ≤ ∑f∗ i ∈N(f) |O∗ i (h)| ∑f∗ i ∈N(f) |O∗ i | ≤ αh. Thus, φ satisfies the group

fairness constraints. We now prove that the mapping ψ satisfies the weighted group fairness constraints. By the above process, we get that the total weight of clients with color h ∈ [m] in C ‡ assigned to a facility f ∈ H is exactly equal to the number of clients of this color assigned to f in the solution (H, φ), i.e., for any f ∈ H and h ∈ [m], we have ∑c‡∈C‡h ψ(c‡ , f) = |{c ∈ Ch | φ(c) = f}|. Then, for any f ∈ H, we have ∑c‡∈C‡ ψ(c‡ , f) = |{c ∈ C | φ(c) = f}|. Thus, for any f ∈ H and h ∈ [m], ∑c‡∈C‡h ψ(c‡ ,f ) ∑c‡∈C‡ ψ(c‡ ,f) = |{c∈Ch|φ(c)=f}| |{c∈C|φ(c)=f}| holds. Since the mapping φ satisfies the group fairness constraints, the mapping ψ satisfies the weighted group fairness constraints.

Lemma 9 implies that there must exist a (4 + ϵ)- approximate solution ψ satisfying the weighted group fairness constraints. To obtain such a solution, the general idea is to reduce the assignment problem to a linear programming problem. The unknown optimal assignment can be naturally expressed in terms of linear inequalities, along with the condition that the assignment is fair. However, the issue is that in general the optimal fractional solution to this linear programming problem is not integral, and we must covert it to integral solution. Naturally, we start with the following linear programming. For any client cj ∈ C ‡ and facility fi ∈ H, we introduce a variable xij denoting how much weight from the client cj is assigned to the facility fi. Note that the value of xij represents the assignment ψ. The goal is to minimize the cost ∑cj∈C‡ ∑fi∈H d(cj , fi)xij satisfying the following conditions.

Constraint (1) ensures that each client cj ∈ C ‡ is assigned to facilities with weight w† (cj). Constraints (2) and (3) capture the group fairness constraints. The above linear programming can be solved in polynomial time, yielding a fractional assignment satisfying the group fairness. To obtain an integral assignment, by using a deterministic rounding method [Bercea et al., 2019] that rounds the feasible fractional assignment obtained to an integral assignment, we have the following result. Note that we now only need to satisfy the group fairness constraints.

Lemma 10. For the DF-k-MED problem, there is a deterministic rounding algorithm that returns an integral assignment ψ with cost at most (4+ϵ)opt with an additive 1 violation for group fairness constraints.

4.3 The Analysis of Running Time

We now bound the running time of Algorithm 1. Indeed, we only need to discuss the iteration of steps 4-5, since all other things can be executed in polynomial time, including constructing coreset, optimizing improvement function, and solving the Weighted Assignment problem. Since the size of the weighted set is |C † | = O(η-2k logn), there are at most |C † |k = (O(η-2k log n))k different multi-sets of size k. Additionally, there are (log1+δ dmax dmin )k = (O(logn))k choices for λi for each i ∈ [k], since the aspect ratio dmax dmin can be assumed to polynomially bounded in n. Therefore, the number of iterations in steps 4-5 of the algorithm can be bounded by (O(η-2k logn))k · (O(logn))k ≤ (O(η-2 logn))k . If k < logn/ log logn, we can obtain (O(η-2 logn))k ≤ (O(η-2 ))k · (logn)logn/ log logn = (O(η-2 ))k · n. Otherwise, logn ≤ O(k log k), implying (O(η-2 logn))k = (O(η-2k log k))k . Therefore, the running time of Algorithm 1 can be bounded by (O(η-2k log k))k · nO(1) . By Lemma 10 and the above discussion, Theorem 1 can be proved.

5 Conclusions

In this paper, we study the doubly constrained fair clustering. Due to the doubly fairness constraints, it is thus a non-trivial task to obtain a solution that satisfies the fairness constraints and meanwhile achieves a small approximation ratio. The main contribution of this paper is a (4+ϵ)-approximation for the DF-k-MED problem, in FPT(k)-time parameterized only by the number of opened facilities. Considering the considerable attention received by the theoretical aspect of the fair clustering problem, we believe that gaining these new parameterized results are of independent interest.

Acknowledgments

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