arXiv CSopen access

Constant-Factor Approximations for Doubly Constrained Fair k-Center, k-Median and k-Means

2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

machine learning, deep learning, neural networks

Constant-Factor Approximations for Doubly Constrained Fair k-Center, k-Median and k-Means Nicole Funk # Department of Informatics, University of Cologne, Germany

Annika Hennes # Heinrich Heine University Düsseldorf, Faculty of Mathematics and Natural Sciences, Germany

Johanna Hillebrand # Heinrich Heine University Düsseldorf, Faculty of Mathematics and Natural Sciences, Germany

Sarah Sturm #

arXiv:2604.16061v1 [cs.DS] 17 Apr 2026

Department of Informatics, University of Bonn, Germany

Abstract We study discrete k-clustering problems in general metric spaces that are constrained by a combination of two different fairness conditions within the demographic fairness model. Given a metric space (P, d), where every point in P is equipped with a protected attribute, and a number k, the goal is to partition P into k clusters with a designated center each, such that a center-based objective function is minimized and the attributes are fairly distributed with respect to the following two fairness concepts: 1) group fairness: We aim for clusters with balanced numbers of attributes by specifying lower and upper bounds for the desired attribute proportions. 2) diverse center selection: Clusters have natural representatives, i.e., their centers. We ask for a balanced set of representatives by specifying the desired number of centers to choose from each attribute. Dickerson, Esmaeili, Morgenstern, and Pena [14] denote the combination of these two constraints as doubly constrained fair clustering. They present algorithms whose guarantees depend on the best known approximation factors for either of these problems. Currently, this implies an 8-approximation with a small additive violation on the group fairness constraint. For k-center, we improve this approximation factor to 4 with a small additive violation. This guarantee also depends on the currently best algorithm for DS-fair k-center given by Jones, Nguyen and Nguyen [22]. For kmedian and k-means, we propose the first constant-factor approximation algorithms. Our algorithms transform a solution that satisfies diverse center selection into a doubly constrained fair clustering using an LP-based approach. Furthermore, our results are generalizable to other center-selection constraints, such as matroid k-clustering and knapsack constraints. 2012 ACM Subject Classification Theory of computation → Facility location and clustering; Computing methodologies → Cluster analysis; Theory of computation → Rounding techniques; Theory of computation → Linear programming Keywords and phrases Clustering, Fairness, Approximation Algorithms, k-center, k-median, k-means Supplementary Material An implementation of the doubly constrained fair k-center algorithm Software: https://github.com/FairClusteringResearch/doubly_fair_clustering Funding Nicole Funk: Funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – Project Number 559931366 Annika Hennes: Funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) - Project 456558332 Johanna Hillebrand: Funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) - Project 459420781 Sarah Sturm: Funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – Project Number 459420781 Acknowledgements We thank Melanie Schmidt for her valuable feedback and advice, Anna Arutyunova for proofreading the manuscript, and Lukas Drexler and Elmar Langetepe for productive initial

Constant-Factor Approximations for Doubly Constrained Fair k-Clustering

discussions. We are also grateful to the three anonymous reviewers whose constructive comments helped improve this paper.

Introduction

With algorithms being used in a wide range of applications that can have a significant impact on individuals and society, fairness in machine learning has become an increasingly important topic in recent years. Much of the work is inspired by the disparate impact effect, which describes how machine learning algorithms may produce biased outcomes that disproportionately affect individual groups based on certain protected attributes. Clustering is a fundamental task in unsupervised learning, making this issue relevant in this context. Arguably, the most popular center-based clustering objectives are k-center, k-median, and kmeans. For the unconstrained versions in general metric spaces, the √ best known approximation factors are 2 for k-center [20, 16], 2 + ϵ for k-median [12] and 3 + 2 2 + ϵ ≈ 5.83 for k-means [7]. Directly addressing the disparate impact effect, demographic fairness notions aim to ensure that protected attributes are fairly represented in the clusters. We say that data points belong to the same group if they share the same protected attribute value. Throughout, we will assume that any data point belongs to exactly one group, i. e., that the groups are disjoint. We also identify groups with different colors. Since the work of Chierichetti, Kumar, Lattanzi and Vassilvitskii[11] initiated the rigorous study of fair clustering, a significant amount of research has emerged on this topic [10, 13], spanning a variety of different fairness notions. Here, we focus on two specific demographic fairness constraints: group fairness and diverse center selection. Our goal will be to construct clusterings that satisfy the combination of these fairness constraints, but first, we will discuss them individually. Group fairness Group fairness concerns the composition of clusters, namely ensuring that the proportion of points from any group in each cluster is within certain bounds. For group fair k-center, k-median, and k-means there exist: a 3-approximation with additive violation of at most 1 [4], a (4 + ϵ)-approximation with violation of ≤ 1 [4, 3], and a 10.66-approximation with violation of ≤ 3 [3], respectively. Diverse center selection Complementing the group fairness notion, diverse center selection aims to ensure fair representation of the groups. As centers are naturally interpreted as representatives of the clusters, this constraint requires that from each group, a certain number of points be selected as centers. We also say that a clustering is diversity-aware when the selected centers satisfy this constraint. For diversity-aware k-center, k-median, and k-means with exact numbers of points per center, there exist: a 3-approximation [22], a 7.081-approximation [32, 25], and a 256-approximation [32, 33] (and a 64-approximation if the distances are Euclidean [32, 38]), respectively. Doubly constrained fair clustering Most works study these two constraints in isolation, but one could argue that, in many applications, it is desirable to achieve both constraints simultaneously. Group fairness alone can be useful to guarantee a range of different opinions and life experiences in a working environment or in a voting group, i. e., a cluster. This can boost productivity or prevent manipulation, such as gerrymandering, but loses its effect if the chosen representatives of the groups are not as diverse and act in their own interests. At the other extreme, selecting only diverse centers without addressing the distributions within

N. Funk, A. Hennes, J. Hillebrand and S. Sturm

the clusters leaves the possibility of manipulation or peer pressure, mitigating the advantages of diverse centers. Dickerson, Esmaeili, Morgenstern, and Pena [14] were the first to study the combination of these two constraints for the k-center problem and coined the term doubly constrained fair clustering. They present algorithms that sequentially solve the two problems to achieve solutions for the doubly constrained problem. The guarantees depend on the order in which the two problems are considered. By first computing a group fair solution, and transforming it into a doubly fair solution, they get a 2αGF -approximation for doubly fair k-center, where αGF is the approximation guarantee of the algorithm used to compute the group fair clustering. Note that their approach requires an algorithm for group fair clustering with no additive violation, which currently does not exist for k-center. Therefore, we will only compare to their results for the other direction, where they first compute an αDS -approximation for diversity-aware k-center and then transform it into a doubly constrained fair solution, which yields a 2(αDS + 1)-approximation overall. While one could easily arrange for diverse center selection by moving centers into their own singleton clusters, to ensure group fairness, clusters usually need to contain multiple points in addition to their selected center. Our contributions We improve on known results for k-center and construct the first constant-factor approximation algorithms for doubly constrained fair k-median and k-means. We improve the currently best known approximation guarantee for doubly constrained fair k-center [14] by a factor of 2. Using the currently best approximation factor for diversity-aware k-center [22], this implies a 4-approximation for doubly constrained fair k-center with an additive violation of at most 2 for the group fairness constraint. We present the first polynomial-time constant-factor approximation algorithms for doubly constrained fair k-median and k-means. For k-median, our√algorithm currently implies a 10.081-approximation, and for k-means, it yields a 291 + 2 290 ≈ 325.06-approximation, both with an additive violation of at most 2 for the group fairness constraint. Our algorithms generalize to combinations of the group fairness constraint with other constraints on the centers, such as matroid and knapsack constraints or individual fairness. Techniques Our algorithms for all three objectives follow the same framework: First, we independently compute a diversity-aware center set using an external approximation algorithm and a (fractional) group fair solution by solving a linear program. Next, we combine the two solutions by rerouting assignments so that only centers from the diversityaware clustering get assigned points. Finally, we compute an integral solution by solving a max flow instance for k-center and a min cost flow instance for k-median and k-means. The idea for the overall framework and the rerouting of assignments is inspired by the work of Ahmadian, Epasto, Kumar and Mahdian [2], who study a special case of group fairness with only upper bounds on the ratios of colors and provide a 3-approximation with additive violation of at most 2 for k-center without over-representation. We significantly adapt their techniques to handle our doubly constrained setting. First, we must incorporate lower bounds into the group fairness constraint. While adapting the linear program is straightforward, it requires a more complex rerouting of assignments to ensure that the lower bounds are still satisfied after reassigning the points. Second, we need to handle the fact that we have to combine two different solutions. They compute a set of centers that have pairwise distances of at least some appropriate threshold, which guarantees that there are at most k centers. The LP solution guarantees that every point has a close LP center, and the lower bound on the pairwise distances of the centers

Constant-Factor Approximations for Doubly Constrained Fair k-Clustering

guarantees that every new center has a close LP center that is not as close to other centers. This allows them to reroute all the mass assigned to an old center in the LP solution to the closest new center, and every new center gets assigned some positive mass. In our case, we do not have such a guarantee, as the diversity-aware solution does not provide a lower bound on the pairwise distances between the centers. Just reassigning the mass in the same way would not work as some centers from the diversity-aware solution might not get assigned any points, violating the requirement that all centers should be active. Therefore, we need to reroute the mass in a more complex way. We ensure that every cluster is assigned some mass, which may require splitting the incoming mass of an LP center appropriately among multiple centers from the diversity-aware solution while maintaining group fairness. Then, we reassign the remaining mass by the approach described above. For the other objectives, we need to refine the rerouting approach further to keep the solution’s cost small. We compare our results with those of [14] for the direction in which they transform a diversity-aware solution into a doubly constrained fair solution. Our algorithm performs the transformation in the same direction, and no applicable algorithm exists for the other direction. Their approach is similar to the framework described above, but differs in that they incorporate the centers computed by the diversity-aware clustering algorithm directly into their linear program for group fairness. Solving the linear program with the given centers causes the problem that some centers might not get assigned any points, i. e., they are not active. To overcome this issue, they replace inactive centers with points from suitable groups inside clusters that are large enough to be split into two group fair clusters. The additional factor of 2 in their approximation guarantee comes from this splitting step, which is not necessary in our approach. They finalize their solution by rounding the assignments by computing a max-flow, while we need to reroute assignments to other centers first before solving a max-flow instance.

1.1

Problem definition

Let (P, d) be a general metric space with |P | = n and k ∈ {1, . . . , n} an integer. A k-clustering is a partition of P into k clusters C1 , . . . , Ck optimizing some objective function. We are considering center-based objectives, where a clustering is induced by a set of centers C ⊆ P with | C | ≤ k and an assignment φ : P → C mapping points to centers. Note that we study the discrete variant of k-clustering, where the set of centers must be a subset of the point set. The cluster with center c is given by C = φ−1 (c). In the k-center objective, our goal is to minimize the maximal distance of any point to its assigned center, i. e., we want to minimize the maximal radius maxp∈P d(p, φ(p)) among the clusters. In k-median, the objective is to P minimize the sum of distances of points to their assigned center, i. e., p∈P d(p, φ(p)), and in k-means it is the sum of squared distances of points to centers that we want to minimize, P i. e., p∈P d(p, φ(p))2 . We study clusterings that satisfy two types of demographic fairness constraints. Both fairness notions rely on a coloring of the points. Let m be some number of colors. For 1 ≤ h ≤ m, we denote the group of points of color h by Ph . We assume that every point in P is assigned exactly one color 1 ≤ h ≤ m, i.e., P = P1 ∪˙ . . . ∪˙ Pm . On the one hand, we want to achieve a fair distribution of colors in the clusters. This means that every color should constitute a certain fraction in every cluster. For every color h, we are given a lower bound ℓh and an upper bound uh on these fractions. To relax this problem, we further allow a small additive violation of these fractional bounds. ▶ Definition 1 (Group fair cluster). For all 1 ≤ h ≤ m, let ℓh , uh be values with 0 ≤ ℓh ≤

N. Funk, A. Hennes, J. Hillebrand and S. Sturm

uh ≤ 1. Let ρ ∈ N. We say that a cluster C is group fair with additive violation ρ if ℓh |C| − ρ ≤ |C ∩ Ph | ≤ uh |C| + ρ for all colors 1 ≤ h ≤ m. We say that a cluster is group fair if ρ = 0. We say that a clustering fulfills the group fairness constraint (GF) if every cluster is group fair. If the lower and upper bounds on the ratios of the groups equal the respective proportions in the overall dataset, we also speak of exact preservation of ratios or short exact group fairness. Additionally, we aim for a fair representation of the colors, formalized by lower and upper bounds on the number of centers per group. P ▶ Definition 2 (Diverse center selection). Given Lh , Uh ∈ N for h ≤ m such that h≤m Lh ≤ P k ≤ h≤m Uh , we say that a set of centers C satisfies the diverse center selection (DS) constraint if Lh ≤ |C ∩ Ph | ≤ Uh for all h ≤ m. The definition in its most general form is also called fair-range clustering; the special case with only lower bounds is also referred to as minority protection; we denote the case Lh = Uh for all h ∈ H by exact diverse center selection. All guarantees with fixed approximation guarantees stated in this paper hold for exact diverse center selection; some even hold for more general cases, see also the section on related work. Our algorithm does not depend on the specific combinatorial structure of the center set and therefore also works for the generalized version, provided appropriate approximation algorithms are available. Throughout, we will consider only instances with feasible solutions.

1.2

Our results

We have two main results; the first is a constant factor approximation algorithm for the doubly constrained fair k-center problem. ▶ Theorem 3. Let γ center be the approximation factor of a given approximation algorithm for DS-fair k-center. There exists an algorithm that computes a (γ center +1)-approximation with GF-violation of ≤ 2 for the doubly constrained fair k-center problem in polynomial time. Using the currently best approximation factor of 3 for k-center with DS by Jones, Nguyen and Nguyen [22], this yields a 4-approximation. ▶ Corollary 4. There exists an algorithm that computes a 4-approximation for the doubly constrained fair k-center problem with a GF-violation of at most 2. The second result extends the techniques of the k-center algorithm to obtain approximation algorithms for the doubly constrained fair k-median problem and the doubly constrained fair k-means problem. ▶ Theorem 5. There exists a polynomial time algorithm that computes a (γ med +3)-approximation with GF-violation of at most 2 for the doubly constrained fair k-median problem, where γ med is the approximation factor of a given approximation algorithm for DS-fair k-median. q √ ( 1 + ( γ means + 1)2 + 1)2 -approximation with GF-violation of at most 2 for the doubly constrained fair k-means problem, where γ means is the approximation factor of a given approximation algorithm for DS-fair k-means. Currently the best algorithm for center fair k-median computes a 7.081-approximation [32, 25] and for k-means a 256-approximation [32, 33], resulting in the following:

Constant-Factor Approximations for Doubly Constrained Fair k-Clustering

▶ Corollary 6. There exists an algorithm that computes a 10.081-approximation with GF-violation of at most 2 for the doubly constrained fair k-median problem. √ 291 + 2 290 ≈ 325.06-approximation with GF-violation of at most 2 for the doubly constrained fair k-means problem. For the special case of doubly constrained fair k-means√under Euclidean Distance we can use the 64-approximation [32, 38] to achieve an 83 + 2 82 ≈ 101.11-approximation with GF-violation of at most 2. We remark that, as we use the approximation algorithms for clustering with diverse centers as opaque-box1 algorithms, our results can also be applied to combine the group fairness constraint with different notions of fairness. Such a notion would need to apply only to the set of centers, e. g., matroid and knapsack constraints [30, 38] or the notion of individual fairness [23, 33].

1.3

Related work

Besides the two specific fairness definitions described above, there is an abundance of different fairness notions. These include, but are not limited to, more constraints focusing on fair distributions of points, such as balance [11], bounded representation [2], and colorful clustering [21]. Other fairness concepts focus on distances, like individual fairness [26] and socially fair clustering [1]. Chierichetti, Kumar, Lattanzi and Vassilvitskii [11] were the first to study the group fairness constraint (albeit not using this name) for the special case of two colors and a specific balance notion. Bercea, Groß, Khuller, Kumar, Rösner, Schmidt and Schmidt [4] presented the first approximation algorithms for group fair clustering for general metric spaces and general bounds on the proportions of groups for an arbitrary number of groups. For the fair k-center problem, there is a deterministic 3-approximation algorithm with additive violation of at most 1 [4] and randomized 3-approximation with no additive violation in expectation [19]. For the exact variant, Bercea et al. [4] provide a 5-approximation algorithm with no additive violation for exact preservation of ratios, and show that it is NP-hard to approximate the assignment version of this problem, i. e., finding the optimal k-center assignment for a given set of centers, better than a factor of 3. For k-median, Bercea et al. [4] and Bera et al. [3] both give algorithms implying a (4 + ϵ)-approximation with an additive violation of at most 1 for the group fairness √ constraint using the recent (2 + ϵ)-approximation for k-median [12]. For k-means, a 5 + 4 2 + ϵ ≈ 10.66-approximation with violation of ≤ 3 is achieved by the algorithm from Bera, Chakrabarty, Flores and Negahbani [3], using the best known approximation for unconstrained k-means [7]. All these results assume that the groups are disjoint. Approximation algorithms for the generalization of non-disjoint groups also exist [3, 19]. Further related for group fairness include the integration of privacy constraints [29], the learning-augmented setting [35], streaming, and the distributed model [5]. We now look at the related work for the diverse center selection constraint. For the k-center objective, there exists a 3-approximation for exact center diversity [22], and a 3approximation for a slight variant of diverse center selection that deals with lower and upper bounds on fractions of the actual proportions of a group in the data set [27]. If color groups are non-disjoint, the problem is inapproximable to any factor, assuming P = ̸ N P [32]. For the most general version of diverse center selection, there exists an FPT 3-approximation that can

https://www.acm.org/diversity-inclusion/words-matter

N. Funk, A. Hennes, J. Hillebrand and S. Sturm

Table 1 Comparison of approximation algorithms for doubly constrained fair k-clustering in general metric spaces. All results hold for exact center diversity; some of them hold for more general cases. Here, ∆ denotes the maximum cluster size in the computed solution, and add. GF viol. denotes the additive violation of the group fairness constraint. The approximation ratios for this work use the currently best diversity-aware algorithms as subroutines: a 3-approximation for k-center [22], a 7.081-approximation for k-median [32, 25], and a 256-approximation for k-means [32, 38]. Objective

Reference

k-center

Dickerson et al. [14] This work

k-median

Zhang et al. [36] Wu et al. [34] This work

k-means

Zhang et al. [36] This work

Approx. ratio

Add. GF viol.

Runtime

8 4

≤3 ≤2

poly poly

O(∆) 4+ε 10.081 √ O( ∆) √ 291 + 2 290 ≈ 325.06

≤5 ≤1 ≤2

poly FPT poly

≤5 ≤2

poly poly

even handle outliers [15]. For k-median and k-means, a result for general p-norm objectives implies eO(1) -approximations for general diverse center selection. In the exact case, Thejaswi, Ordozgoiti and Gionis [32] show that the problem for the k-median objective can be reduced to the matroid median problem in polynomial time. This result can also be generalized to other objectives, implying a 7.081-approximation for k-median and a 256-approximation for k-means with exact diverse center selection, using the best known guarantees for the matroid version of the respective objective [25, 33]; where the k-means variant allows for a 64-approximation if the distances are Euclidean [32, 38]. In the FPT-regime, randomized (1 + 2e + ϵ)- and (1 + 8e + ϵ)-approximations for general diversity-aware k-median and k-means can be achieved, respectively [31]. For Euclidean spaces, (1 + ϵ)-approximations are possible for both objectives under the diverse center selection constraint [37]. Further related work in the realm of diverse center selection includes distributed models [6] and the streaming setting [6, 17]. For doubly constrained fair clustering, the landscape of related work is sparser. Only for k-center, there exists a constant-factor approximation algorithm [14]. For k-median, there is an FPT-time approximation algorithm by [34] that achieves an approximation ratio of 4 + ϵ with an additive violation of at most 1 for the group fairness constraint. For general p-norm objectives, there is a polynomial-time algorithm by [36] that achieves an approximation ratio of O(∆1/p ) with an additive violation of at most 5, where ∆ is the maximum cluster size in the computed solution. Table 1 summarizes the results for doubly constrained fair clustering in general metric spaces, comparing our results to the state-of-the-art. Lastly, we provide a brief overview of additional important center constraints that our algorithm can handle. There exists a 3-approximation for matroid k-center [8], a 7.081approximation for matroid median [25], and a 256-approximation for matroid means [33], which is improved to 64 in Euclidean spaces [38]. For knapsack constraints, the factors are 3 [20], 6.387 + ϵ [18] and 1128 + ϵ [38] for k-center, k-median and (Euclidean) k-means.

Constant-Factor Approximations for Doubly Constrained Fair k-Clustering

A 4-approximation for k-center with center diversity and group fairness constraints

First, we give an overview of the algorithm, followed by a detailed description of the individual steps. As an initial step, compute a fractional solution (x, y) to the k-center clustering problem with only the group fairness constraint using linear programming, where x represents a fractional assignment of points to centers, and y indicates which points receive mass from other points in x, i.e., are used as centers in (x, y). Furthermore, we compute a set of centers CDS satisfying center diversity using a known approximation algorithm for this problem. As a next step, we reroute the mass in (x, y) such that only the points in CDS are used as centers. This yields a fractional solution satisfying center diversity and group fairness. Lastly, we convert the fractional assignment to an integral one by using a max flow with lower bounds. To discuss the algorithm in more detail, we divide it into four components, which are later formalized in Algorithm 1. 1. Compute a set of centers CDS that fulfills center diversity 2. Compute a fractional group fair solution (x, y) 3. Reroute mass in x such that only points in CDS receive positive mass → (x′ , y ′ ) 4. Compute an integral point assignment → (x′′ , y ′′ )

2.1

Center diversity

To guarantee our solution fulfills the DS constraint we use an existing algorithm for diversityaware k-center as an opaque-box algorithm. In the following, let CDS be the returned set of centers that satisfy the DS constraint, and γ center be the approximation factor of the algorithm. Currently, the best known algorithm for diversity-aware k-center is the 3-approximation by Jones et al. [22] with O(nk) running time. If the combination of group fairness with another constraint is desired, a corresponding approximation algorithm can be used instead.

2.2

Group fairness

We formulate a linear program to obtain an initial fractional group fair clustering. We use a matrix of variables x representing the assignment from points to centers, i.e., xij denotes the amount of mass sent from point j ∈ P to point i ∈ P , i. e., the amount by which a point j is assigned to a center i. Additionally, we compute a vector of variables y, where yi can be interpreted as the amount to which i ∈ P is opened as a center. X xij = 1 ∀j ∈ P (LP-1.1) i∈P

xij ≤ yi X yi ≤ k

∀i, j ∈ P

(LP-1.2) (LP-1.3)

i∈P

xij ≤ uh

j∈Ph

xij

∀h ∈ H, i ∈ P

(LP-1.4)

xij

∀h ∈ H, i ∈ P

(LP-1.5)

∀j ∈ P, i ∈ P : d(i, j) > λ

(LP-1.6)

∀i, j ∈ P

(LP-1.7)

j∈P

xij ≥ ℓh

X j∈P

j∈Ph

xij = 0 0 ≤ xij , yi ≤ 1

N. Funk, A. Hennes, J. Hillebrand and S. Sturm

We denote the linear program by LP(λ). Note that the k-center objective function is not linear. However, we can control the cost of a feasible solution via constraint (LP-1.6), which ensures that points are not assigned to centers farther than λ away. Combining this with a search over all possible values of λ allows us to drop the objective function. The group fairness (as described in Definition 1) is enforced by constraints (LP-1.4) and (LP-1.5). This linear program is a correct formalization of k-center clustering with group fairness constraint. To see this, we prove that any feasible k-center clustering satisfying group fairness corresponds to a feasible solution for LP(λ) when λ is at least the objective value of the clustering. The proof of the following two lemmas can be found in Section A. ▶ Lemma 7. Let (C, φ) be a feasible k-center clustering satisfying GF with objective value λC . Then, (x, y) defined by ( ( 1 if i = φ(j) 1 if i ∈ C xij = and yi = 0 otherwise 0 otherwise is a feasible solution for LP(λC ). ▶ Lemma 8. Let (x, y) be a feasible integral solution for LP(λ). Then, (C, φ) defined by C = {i ∈ P | yi = 1}

and

φ(j) = arg max xij i∈P

for all j ∈ P

is a feasible k-center clustering satisfying group fairness with objective value λ. We choose the value of λ as follows. It should be large enough such that LP(λ) allows for a feasible solution. For this, let λLP denote the minimal value such that LP(λLP ) has a solution. Further, λ should be large enough such that the γ center -approximation for k-center with DS has cost upper bounded by γ center ·λ. For this, let λDS be minimal such that the γ center -approximation returns a solution with exactly k centers and value of at most γ center ·λDS . Now, we set λ := max{λLP , λDS }. We can upper bound the value of λ by the value of an optimal solution satisfying both GF and DS. ▶ Lemma 9. Let OPTGF+DS be the value of an optimal k-center solution satisfying GF and DS. Then, λ := max{λLP , λDS } ≤ OPTGF+DS . Proof. Let OPTGF and OPTDS denote the values of an optimal k-center clustering satisfying GF and DS, respectively. By Lemma 7, LP(OPTGF ) contains a feasible solution. This implies λLP ≤ OPTGF . Let costDS denote the cost of the solution computed by the γ center approximation for k-center with DS. It is costDS ≤ γ center · OPTDS . We set λDS to the minimal value such that costDS ≤ γ center ·λDS . Then, λDS ≤ OPTDS . Any solution satisfying both GF and DS is also a feasible solution for GF or DS, respectively. Hence, OPTGF ≤ OPTGF + DS and OPTDS ≤ OPTGF + DS . Putting everything together yields max{λLP , λDS } ≤ max{OPTGF , OPTDS } ≤ OPTGF + DS . ◀

2.3

Rerouting fractional assignments

Let (x, y) be the (fractional) group fair solution computed by solving the LP optimally, and CDS be the set of diverse centers computed by a γ center -approximation for k-center with DS constraint. If xij > 0 for some j ∈ P , the point i can be considered as a center in this solution. We want to reroute mass to the centers in CDS , such that positive mass is only sent to points in CDS . Meanwhile, we want to ensure that all centers in CDS get some positive

Constant-Factor Approximations for Doubly Constrained Fair k-Clustering

xqj

xpj

1 x′i1 j = xpi pi +xpi xpj + xqj 1

xpi1 i1

2 x′i2 j = xpi pi +xpi xpj 1

xpi2 i2

Figure 1 Rerouting the mass outgoing at a point j. There are two centers i1 , i2 ∈ CDS . The point j covers both cases: there is a point p ∈ N (CDS ) and a point q ̸∈ N (CDS ) that j sends mass to. The mass xpj is split and rerouted to the two centers i1 , i2 ∈ CDS proportionally to the x c mass they send to p. Center ic gets an xpi pi -fraction of xpj for c = 1, 2. Let us assume that +xpi2 1 i1 = argmini∈CDS d(q, i). Then, the mass xqj is fully rerouted to i1 . The original mass assignments are indicated using solid black lines; the rerouted mass assignments are shown with blue dashed lines. Omitted edges correspond to 0 assignments.

P mass. That is, we construct (x′ , y ′ ) such that {i ∈ P | j∈P x′ij > 0} = CDS , while ensuring that the cost does not increase too much. In this context, we need the notion of a point’s neighborhood. For a point j ∈ P , we define the set N (j) := {i ∈ P | xij > 0} of all the points that j sends positive mass to (i. e., is assigned to in the fractional solution). For a set of S points P ′ ⊆ P , we define N (P ′ ) := j∈P ′ N (j). The overall idea is to take all the mass incoming at some point p ∈ P in the LP solution (x, y) and reroute it to a “nearby” center in CDS if this is possible. We have to be careful that this does not change the color proportions. Then, as (x, y) fulfills group fairness, the newly formed clusters are also group fair. Consider a point p ∈ P that gets some mass in P the current solution, i.e., j∈P xpj > 0. Depending on p’s position relative to the centers in CDS , we decide how to reroute the incoming mass at p. We want to prevent any center in CDS from becoming empty (i.e., it gets no mass assigned). P By the first constraint of the LP, i∈P xij = 1, every point, particularly every center in CDS , must possess some outgoing mass in the LP solution (x, y). That is, for every c ∈ CDS , the set N (c) is non-empty. To ensure that mass is sent to a point c ∈ CDS , we reroute mass sent to a point p ∈ N (c) to c. However, these sets might overlap, and if we sent all incoming mass at p ∈ N (c) to c, there might not be any mass left to send to some other center that has p in its neighborhood. To circumvent this problem, we proportionally split the mass sent to a point p ∈ N (CDS ) among all points c ∈ CDS with p ∈ N (c). A center i ∈ CDS gets as much mass from j ∈ P with xp,j > 0 as it sends to p, proportional to the masses sent from all centers i′ ∈ CDS to p. In the remaining case that p ̸∈ N (CDS ), p gets mass solely from points that are not desired P centers themselves. In this case, we can safely reroute all mass j∈P xpj to some nearby center in CDS . To keep the distances small, we choose the center i ∈ arg mini′ ∈CDS d(p, i′ ) that is closest to p. Formally, a new fractional solution (x′ , y ′ ) is defined as follows: ( yi′ =

if i ∈ CDS

otherwise

(rerouting-y)

N. Funk, A. Hennes, J. Hillebrand and S. Sturm

P CDS ×H

CDS

t A4 A1

A3 A2

Figure 2 Flow network to find the final assignment of points to centers. Every point in p ∈ P has a node representing it, which has an edge in A1 to the node s. In the figure, these nodes are colored blue or red to represent the color hp of p. Every such node has an edge in A2 to every node corresponding to a pair of a center c ∈ CDS and the color hp , i. e., (c, hp ) ∈ CDS ×H, which are colored accordingly in the figure. Each pair of center and color (c, hp ) has an edge in A3 to a node representing the center c in the pair. Each of these nodes corresponding to a center c ∈ CDS has an edge in A4 connecting it to the node t.

and x′ij =

P  p∈N (i) P

xpi

c∈CDS : p∈N (c)

xpc

xpj +

p∈θ −1 (i) xpj

0

if i ∈ CDS

(rerouting-x)

otherwise,

where θ : P \ N (CDS ) → CDS with ( p if p ∈ CDS θ(p) = i with i ∈ argmini′ ∈CDS d(p, i′ ), otherwise Figure 1 schematically visualizes how the mass emitted from a point j is rerouted to centers in CDS . We can show that the rerouted solution (x′ , y ′ ) is a feasible solution to LP((γ center +1)λ) such that y ′ is integral. Further, every c ∈ CDS gets a mass of at least 1 assigned. We defer the proof to Section A. ▶ Lemma 10. Let (x, y) be a feasible solution for LP(λ) and let (x′ , y ′ ) be the solution achieved through the rerouting described above. Then the following properties hold: 1. (x′ , y ′ ) is a feasible solution to LP((γ center +1)λ) P ′ 2. j∈P xij ≥ 1 for all i ∈ CDS 3. y ′ is integral.

2.4

Final fair assignment

After the rerouting step (see Section 2.3), we have an assignment that is group fair and satisfies the diverse center selection constraint. However, the assignment x′ is still fractional. To achieve the final integral assignment of points to centers, we build a network graph and solve a max flow problem with lower bounds on it, similar to [2]. This is done as follows: Let G = (V, E), where V = {s, t} ∪ P ∪ {(i, h) | i ∈ CDS , h ∈ H} ∪ CDS and E = A1 ∪ A2 ∪ A3 ∪ A4 . The set of edges A1 = {(s, j) | j ∈ P } connects all points in P to the source. Each point j ∈ P is connected to a center-color-node (i, h), if j ∈ Ph and x′ij = 1. More formally A2 = {(j, (i, h)) | i ∈ CDS , j ∈ Ph , x′ij > 0}. The edges in A1 and A2 have capacity 1. Each of the color-center-nodes (i, h) is connected to its corresponding center i,

Constant-Factor Approximations for Doubly Constrained Fair k-Clustering

thus A3 = {((i, h), i) | i ∈ CDS , h ∈ H}. The capacities on these edges ensure that each center receives (nearly) the same amount of flow of each color as it does in the fractional group fair P solution. Since j∈Ph x′ij is not necessarily integral, lower and upper bounds on the edges P P are introduced; the lower bound is ⌊ j∈Ph x′ij ⌋ and the upper bound is ⌈ j∈Ph x′ij ⌉. Lastly, the set of edges A4 = {(i, t) | i ∈ CDS } connects all center points to the sink t. These edges are used to ensure that each cluster center receives (nearly) as much total flow as it received P in the fractional solution, but again j∈P x′ij is not necessarily integral. Each edge has the P P lower bound ⌊ j∈P x′ij ⌋ and the upper bound ⌈ j∈P x′ij ⌉ (see Figure 2). The important property of a max flow we use here is that in a network with integral capacities and integral demands, there always exists a feasible assignment that is integral. Since there is a flow with value |P | (using x′ ), there is also an integral flow with value |P |. Let x′′ be the integral assignment from the flow. Our final solution is given by the pair (y ′ , x′′ ). This step can introduce an additive violation of 2. ▶ Lemma 11 (Group fairness – k-center). For each center i and each color h it holds that X X X lh x′′ij − 2 ≤ x′′ij ≤ uh x′′ij + 2. j∈P

j∈Ph

j∈P

Proof (analogous to [2]). The full proof for Lemma 11 can be found in Section A.

◀

Algorithm 1 Doubly constrained fair k-center

: point set P , distance metric d, k ∈ N, group fairness bounds ℓh , uh ∈ N for all h ∈ H, algorithm for center constraint Acenter Output : center set C and assignment φ 1 CDS , costDS ← centers and objective value returned by Acenter (P, d, k) 2 R ← {d(p, q) | p, q ∈ P } DS 3 λ ← min{r ∈ R | r ≥ costDS / γ center } GF 4 λ ← min{r ∈ R | LP(r) has a solution} LP 5 λ ← max{λ , λDS } |H| 6 (x, y) ← optimal (fractional) solution for LP(λ) under GF constraints ℓ, u ∈ N ′ ′ 7 (x , y ) ← rerouting of (x, y) as specified in Equations (rerouting-x) and (rerouting-y) ′′ ′′ 8 (x , y ) ← final integral assignment via max flow as described in Section 2.4 ′′ 9 C ← {i ∈ P | yi = 1} 10 for j ∈ P do 11 φ(j) ← arg maxi∈P x′′ij Input

return (C, φ)

This construction results in Theorem 3. We defer the full proof to Section A. ▶ Theorem 3. Let γ center be the approximation factor of a given approximation algorithm for DS-fair k-center. There exists an algorithm that computes a (γ center +1)-approximation with GF-violation of ≤ 2 for the doubly constrained fair k-center problem in polynomial time.

An Algorithm for k-median/k-means with center diversity and group fairness constraints

In this section, we look at the doubly fair clustering problem under the k-median and k-means objective functions. The basic structure of the algorithm we use for these objectives

N. Funk, A. Hennes, J. Hillebrand and S. Sturm

is the same as for the k-center objective described in Section 2. We again use a fractional LP solution that fulfills group fairness and reroute it such that it uses centers we obtain via an opaque-box algorithm for center diversity. The resulting fractional assignment is then rounded via a min cost flow procedure. In the following, we describe the steps of the algorithm for these cost functions and prove its correctness. For notational simplicity we P P describe the k-median cost of a solution (x, y) by cost(x, y) = i∈P j∈P xij d(i, j) and the P P k-means cost by cost2 (x, y) = i∈P j∈P xij d(i, j)2 .

3.1

Center diversity

We find a center fair solution (CDS , φ) via an opaque-box algorithm for the respective problem. For notation reasons, we can interpret this solution as an integral assignment (xDS , y DS ) with yiDS = 1 if and only if i ∈ CDS and xDS ij = 1 iff φ(j) = i. Let γ med and γ means be the resulting approximation factors, respectively. The currently best available approximation algorithms for diverse center selection for these objectives are the following: For k-median with DS, Thejaswi et al. [32] give a reduction to the matroid median problem, allowing a ρ-approximation algorithms for the matroid median problem to be used to compute a ρ-approximation for k-median with DS. Currently the best known algorithm for the matroid median problem is the 7.081-approximation algorithm by Krishnaswamy et al. [25]. The reduction by Thejaswi et al. [32] can also be modified to reduce k-means with DS to the facility location problem with ℓp -norm cost under matroid constraint, where p = 2, introduced by Vakilian and Yalçıner [33]. For this, we only need to set the opening costs of every facility to 0 in addition to the construction of the k-median reduction. As the number of opened facilities is bounded by the partition matroids constructed in the reduction, the arguments by Thejaswi et al. apply here as well. Vakilian and Yalçıner [33] also give a 16p approximation for the facility location problem with ℓp -norm cost under matroid constraint, meaning we can use it to obtain a 256-approximation for k-means with DS. For the special case of Euclidean Distance we can also use the construction by Thejaswi et al. [32] to reduce from the matroid means problem to k-means with DS. This allows us to use the 64-approximation algorithm for matroid means under Euclidean Distance by Zhao et al. [38].

3.2

Group fairness

The following relaxed LP finds a feasible assignment satisfying the GF constraint and minimizes the k-median objective function X minimize xij · d(i, j)2 (LP-Med/LP-Means) i,j∈P

subject to

xij = 1

∀j ∈ P

(LP-2.1)

xij ≤ yi X yi ≤ k

∀i, j ∈ P

(LP-2.2)

i∈P

(LP-2.3)

i∈P

xij ≤ αh

x∈P h

xij

∀h ∈ H, i ∈ P

(LP-2.4)

xij

∀h ∈ H, i ∈ P

(LP-2.5)

∀i, j ∈ P

(LP-2.6)

x∈P

x∈P h

xij ≥ βh

X x∈P

0 ≤ xij ,yi ≤ 1

Constant-Factor Approximations for Doubly Constrained Fair k-Clustering

θ(p)

pi )xpi (1 − xpi +x pj

pi (1 − xpi +x ) xpj pj

xpi

xpj

xpi xpi +xpj xpj

xpi xpi +xpj xpi

Figure 3 Rerouting of the mass arriving on p. The solution (x, y) is depicted by the black arrows. The blue dashed arrows show the rerouting back to i ∈ CDS from p ∈ N (i). The red dashed arrows show the nearest neighbor rerouting of the remaining mass.

Note that the LP is in large parts identical to the one in section 2. The only difference is that both the k-median and k-means objective function are linear, so instead of using Equation (LP-1.6) we now add it as proper objective function to the LP. Which objective function (LP-Med or LP-Means) is used depends on if we are interested in the k-median or the k-means problem. Analogously to Lemma 7 and Lemma 8 it can be shown how to obtain clustering solutions from the LP and the other way round. In the following we denote by (x, y) an optimal solution to the above relaxed LP. Since the algorithm largely works the same for both objectives, we often do not specify which one is used except for cases where it is relevant. Note that the cost of (x, y) is a lower bound for the cost of the optimal doubly fair solution. This holds for both the k-median and the k-means cost function.

3.3

Rerouting

We use the center set CDS from Section 3.1 and reroute the point assignments of (xLP , y LP ) in a way that the following hold: the resulting solution (x′ , y ′ ) is a feasible solution to the LP P for all i ∈ CDS it holds j∈P xij ≥ 1 we can bound the cost of the resulting solution by the following: cost(x′ , y ′ ) ≤ 3 · cost(x, y) + cost(xDS , y DS ) in the k-median case cost2 (x′ , y ′ ) ≤ (1 + p2 + (1 + p12 )(2 + q 2 )) cost2 (x, y) + (1 + p12 )(1 + q12 ) cost2 (xDS , y DS ) for p, q > 0 in the k-means case all yi′ are integral We first focus on the second requirement. For i ∈ CDS we look at the set N (i) := {p ∈ P | xpi > 0} which is the set of points that get assigned positive mass from i in (x, y). The main idea is to redirect the mass that is assigned to a point p ∈ N (i) such that i gets assigned a share of this mass that is equivalent to xpi . After we have done this for all i, p, we reroute the remaining mass that arrives at p by sending it to the nearest neighbor of p in CDS . For this we use the same mapping function θ : {i ∈ P | yi > 0} → CDS as in Section 2.3. x We denote by rpi := P pi x the ratio of xpi to the total mass of assignments on p. Note l∈P

that rpi = 0 if xpi = 0. Using this notation we define (x′ , y ′ ) the following way:

N. Funk, A. Hennes, J. Hillebrand and S. Sturm

yi′ =

( 1

if i ∈ CDS

otherwise

and x′ij =

i p∈N (i) rp xpj +

p∈θ −1 (i) (1 −

l′ l′ ∈CDS rp )xpj

if i ∈ CDS otherwise

An example for this rerouting can be seen in Figure 3. The main difference of this rerouting step to the rerouting in Section 2.3 is that a point i ∈ CDS now does not get all the mass that is assigned to a point p ∈ N (i) (even if he is the only center sending mass there), but only a fraction of it that is equivalent to xpi . This property will later be important when we are bounding the cost of this solution. The following lemmas show that (x′ , y ′ ) do indeed have the desired properties. We defer the corresponding proofs to Section B. Note that the solutions (x′ , y ′ ) depend on the objective function (k-median or k-means), since it is used in the LP in Section 3.2 and the respective opaque-box algorithm in Section 3.1. P ▶ Lemma 12. (x′ , y ′ ) is a feasible solution to the LP in Section 3.2. It holds j∈P x′ij ≥ 1 for all i ∈ CDS . All yi′ in this solution are integral. ▶ Lemma 13 (Cost k-median). For the k-median cost of (x′ , y ′ ) the following holds: cost(x′ , y ′ ) ≤ 3 · cost(x, y) + cost(xDS , y DS ). ▶ Lemma 14 (Cost k-means). For the k-means cost of (x′ , y ′ ) the following holds for p, q > 0: cost2 (x′ , y ′ ) ≤ (1 + p2 + (1 +

3.4

1 1 1 )(2 + q 2 )) cost2 (x, y) + (1 + 2 )(1 + 2 ) cost2 (xDS , y DS ). 2 p p q

Final fair assignment

In this section, we show how to round the fractional assignments x′ to get an integral solution with small additive violation of the group fairness constraint. We show that the resulting solution (x′′ , y ′ ) has the same cost as (x′ , y ′ ). For this, we use the same min cost flow construction as Bercea et al. use in [4] to round their essentially fair clustering solutions. Similarly to the construction used in Section 2.4 the vertex set V is given by V = {s, t} ∪ P ∪ {(i, h) | i ∈ CDS , h ∈ H} ∪ CDS and the set E of edges is given by E = A1 ∪ A2 ∪ A3 ∪ A4 , where A1 = {(s, j) | j ∈ P }, A2 = {(j, (i, h) | j ∈ P, i ∈ CDS , h ∈ H, x′ij > 0}, A3 = {((i, h), i) | i ∈ CDS , h ∈ H} and A4 = {(i, t) | i ∈ CDS }. All edges have unit capacity. A2 is the only edge set that has nonzero cost. An edge (p, (i, h)) ∈ A2 has cost d(p, i) in the k-median case and cost d(p, i)2 in the k-means case. The node balances are defined as follows: s has balance |P | All p ∈ P have balance 0 P All (i, h) ∈ CDS ×H have balance −(⌊ j∈Ph x′ij ⌋) P P P All i ∈ CDS have balance −(⌊ j∈P x′ij ⌋ − h∈H ⌊ j∈Ph x′ij ⌋) P P t has balance −(|P | − i∈CDS ⌊ j∈P x′ij ⌋) The structure of this min cost flow can be seen in Figure 2 since it is identical to the structure of the max flow instance used in Section 2.4. Since all capacities and balances are integral, we can find an integral solution to the flow instance that has minimal cost. We call the assignment we extract from this MinCostflow-solution x′′ . We show that it satisfies group fairness with an additive violation of 2:

Constant-Factor Approximations for Doubly Constrained Fair k-Clustering

▶ Lemma 15 (Group fairness – k-median, k-means). For each center i and each color h it holds that X X X lh x′′ij − 2 ≤ x′′ij ≤ uh x′′ij + 2. j∈P

j∈Ph

j∈P

The final solution is then obtained via the pair (x′′ , y ′ ). We defer the proof that this results in Theorem 5 to Section B. ▶ Theorem 5. There exists a polynomial time algorithm that computes a (γ med +3)-approximation with GF-violation of at most 2 for the doubly constrained fair k-median problem, where γ med is the approximation factor of a given approximation algorithm for DS-fair k-median. q √ ( 1 + ( γ means + 1)2 + 1)2 -approximation with GF-violation of at most 2 for the doubly constrained fair k-means problem, where γ means is the approximation factor of a given approximation algorithm for DS-fair k-means.

Conclusion

We study doubly constrained fair k-clustering problem, requiring both group fairness within clusters and diverse center selection among representatives. Via a modular and extendable approach that uses an LP-based rerouting and rounding routine, we obtain a 4-approximation for k-center and the first constant-factor approximations for k-median and k-means in general metrics. Natural next steps include proving nontrivial lower bounds and eliminating the additive violation. Further, developing non-sequential algorithms that enforce both fairness constraints directly might enable better approximation guarantees.

N. Funk, A. Hennes, J. Hillebrand and S. Sturm

References 1

8 9

10 11

Mohsen Abbasi, Aditya Bhaskara, and Suresh Venkatasubramanian. Fair clustering via equitable group representations. In Madeleine Clare Elish, William Isaac, and Richard S. Zemel, editors, FAccT ’21: 2021 ACM Conference on Fairness, Accountability, and Transparency, Virtual Event / Toronto, Canada, March 3-10, 2021, pages 504–514. ACM, 2021. doi: 10.1145/3442188.3445913. Sara Ahmadian, Alessandro Epasto, Ravi Kumar, and Mohammad Mahdian. Clustering without over-representation. In Ankur Teredesai, Vipin Kumar, Ying Li, Rómer Rosales, Evimaria Terzi, and George Karypis, editors, Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2019, Anchorage, AK, USA, August 4-8, 2019, KDD ’19, pages 267–275, New York, NY, USA, 2019. ACM. doi:10.1145/3292500.3330987. Suman Kalyan Bera, Deeparnab Chakrabarty, Nicolas Flores, and Maryam Negahbani. Fair algorithms for clustering. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d’Alché-Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 4955–4966, 2019. URL: https://proceedings.neurips.cc/paper/2019/hash/ fc192b0c0d270dbf41870a63a8c76c2f-Abstract.html. Ioana Oriana Bercea, Martin Groß, Samir Khuller, Aounon Kumar, Clemens Rösner, Daniel R. Schmidt, and Melanie Schmidt. On the cost of essentially fair clusterings. In Dimitris Achlioptas and László A. Végh, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019, Massachusetts Institute of Technology, Cambridge, MA, USA, September 20-22, 2019, volume 145 of LIPIcs, pages 18:1–18:22. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs. APPROX-RANDOM.2019.18. Matteo Ceccarello, Andrea Pietracaprina, and Geppino Pucci. Fast and accurate fair k-center clustering in doubling metrics. In Tat-Seng Chua, Chong-Wah Ngo, Ravi Kumar, Hady W. Lauw, and Roy Ka-Wei Lee, editors, Proceedings of the ACM on Web Conference 2024, WWW 2024, Singapore, May 13-17, 2024, pages 756–767. ACM, 2024. doi:10.1145/3589334. 3645568. Matteo Ceccarello, Andrea Pietracaprina, Geppino Pucci, and Federico Soldà. Scalable and space-efficient robust matroid center algorithms. J. Big Data, 10(1):49, 2023. URL: https://doi.org/10.1186/s40537-023-00717-4, doi:10.1186/S40537-023-00717-4. Moses Charikar, Vincent Cohen-Addad, Ruiquan Gao, Fabrizio Grandoni, Euiwoong Le, and Ernest Van Wijland. An Improved Greedy Approximation for (Metric) k-Means. In 2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS), pages 233–240, Los Alamitos, CA, USA, dec 2025. IEEE Computer Society. URL: https:// doi.ieeecomputersociety.org/10.1109/FOCS63196.2025.00016, doi:10.1109/FOCS63196. 2025.00016. Danny Z. Chen, Jian Li, Hongyu Liang, and Haitao Wang. Matroid and knapsack center problems. Algorithmica, 75(1):27–52, 2016. doi:10.1007/s00453-015-0010-1. Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Maximum flow and minimum-cost flow in almost-linear time. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 612–623, 2022. doi:10.1109/FOCS54457.2022.00064. Anshuman Chhabra, Karina Masalkovaite, and Prasant Mohapatra. An overview of fairness in clustering. IEEE Access, 9:130698–130720, 2021. doi:10.1109/ACCESS.2021.3114099. Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii. Fair clustering through fairlets. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors, Advances in Neural Information Processing Systems 30: Annual Conference on

Constant-Factor Approximations for Doubly Constrained Fair k-Clustering

15 16 17

20 21 22

Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 5029–5037, 2017. URL: https://proceedings.neurips.cc/paper/2017/hash/ 978fce5bcc4eccc88ad48ce3914124a2-Abstract.html. Vincent Cohen-Addad, Fabrizio Grandoni, Euiwoong Lee, Chris Schwiegelshohn, and Ola Svensson. A (2+ϵ)-approximation algorithm for metric k-median. In Michal Koucký and Nikhil Bansal, editors, Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025, pages 615–624. ACM, 2025. doi:10.1145/ 3717823.3718299. John Dickerson, Seyed A. Esmaeili, Jamie Morgenstern, and Claire Jie Zhang. Sok: Fair clustering: Critique, caveats, and future directions. In IEEE Conference on Secure and Trustworthy Machine Learning, SaTML 2025, Copenhagen, Denmark, April 9-11, 2025, pages 698–713. IEEE, 2025. doi:10.1109/SaTML64287.2025.00044. John P. Dickerson, Seyed A. Esmaeili, Jamie H. Morgenstern, and Claire Jie Zhang. Doubly constrained fair clustering. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023, 2023. URL: http://papers.nips.cc/paper_files/ paper/2023/hash/2ab87e2179b8ea209b52463802d62560-Abstract-Conference.html. Ameet Gadekar. Tight fpt approximations for fair k-center with outliers. 2026. URL: https: //arxiv.org/abs/2602.05476, arXiv:2602.05476, doi:10.48550/arXiv.2602.05476. Teofilo F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theor. Comput. Sci., 38:293–306, 1985. doi:10.1016/0304-3975(85)90224-5. Longkun Guo, Zeyu Lin, Chaoqi Jia, and Chao Chen. Improved streaming algorithm for fair k-center clustering. In Sven Koenig, Chad Jenkins, and Matthew E. Taylor, editors, Fortieth AAAI Conference on Artificial Intelligence, Thirty-Eighth Conference on Innovative Applications of Artificial Intelligence, Sixteenth Symposium on Educational Advances in Artificial Intelligence, AAAI 2026, Singapore, January 20-27, 2026, pages 36946–36954. AAAI Press, 2026. URL: https://doi.org/10.1609/aaai.v40i43.41022, doi:10.1609/AAAI. V40I43.41022. Anupam Gupta, Benjamin Moseley, and Rudy Zhou. Structural iterative rounding for generalized k-median problems. Math. Program., 212(1):581–634, 2025. doi:10.1007/ s10107-024-02119-7. Elfarouk Harb and Ho Shan Lam. KFC: A scalable approximation algorithm for $k$-center fair clustering. In Hugo Larochelle, Marc’Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL: https://proceedings.neurips.cc/paper/2020/ hash/a6d259bfbfa2062843ef543e21d7ec8e-Abstract.html. Dorit S. Hochbaum and David B. Shmoys. A unified approach to approximation algorithms for bottleneck problems. J. ACM, 33(3):533–550, 1986. doi:10.1145/5925.5933. Xinrui Jia, Kshiteej Sheth, and Ola Svensson. Fair colorful k-center clustering. Math. Program., 192(1):339–360, 2022. doi:10.1007/s10107-021-01674-7. Matthew Jones, Huy L. Nguyen, and Thy Dinh Nguyen. Fair k-centers via maximum matching. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 4940–4949. PMLR, 2020. URL: http://proceedings.mlr.press/v119/jones20a.html. Christopher Jung, Sampath Kannan, and Neil Lutz. Service in Your Neighborhood: Fairness in Center Location. In Aaron Roth, editor, 1st Symposium on Foundations of Responsible Computing (FORC 2020), volume 156 of Leibniz International Proceedings in Informatics (LIPIcs), pages 5:1–5:15, Dagstuhl, Germany, 2020. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC. 2020.5, doi:10.4230/LIPIcs.FORC.2020.5.

N. Funk, A. Hennes, J. Hillebrand and S. Sturm

27 28

Ravishankar Krishnaswamy, Amit Kumar, Viswanath Nagarajan, Yogish Sabharwal, and Barna Saha. The matroid median problem. In Dana Randall, editor, Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, pages 1117–1130. SIAM, 2011. doi:10. 1137/1.9781611973082.84. Ravishankar Krishnaswamy, Shi Li, and Sai Sandeep. Constant approximation for k-median and k-means with outliers via iterative rounding. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 646–659. ACM, 2018. doi:10.1145/3188745.3188882. Sepideh Mahabadi and Ali Vakilian. Individual fairness for k-clustering. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 6586–6596. PMLR, 2020. URL: http://proceedings.mlr.press/v119/mahabadi20a.html. Huy Le Nguyen, Thy Dinh Nguyen, and Matthew Jones. Fair range k-center. CoRR, abs/2207.11337, 2022. arXiv:2207.11337, doi:10.48550/arXiv.2207.11337. James B. Orlin. Max flows in o(nm) time, or better. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013, STOC ’13, pages 765–774, New York, NY, USA, 2013. ACM. doi:10.1145/2488608.2488705. Clemens Rösner and Melanie Schmidt. Privacy preserving clustering with constraints. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, Prague, Czech Republic, July 9-13, 2018, volume 107 of LIPIcs, pages 96:1–96:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. doi:10.4230/LIPIcs.ICALP.2018.96. Chaitanya Swamy. Improved approximation algorithms for matroid and knapsack median problems and applications. ACM Trans. Algorithms, 12(4):49:1–49:22, 2016. doi:10.1145/ 2963170. Suhas Thejaswi, Ameet Gadekar, Bruno Ordozgoiti, and Aristides Gionis. Diversity-aware clustering: Computational complexity and approximation algorithms. CoRR, abs/2401.05502, 2024. arXiv:2401.05502, doi:10.48550/arXiv.2401.05502. Suhas Thejaswi, Bruno Ordozgoiti, and Aristides Gionis. Diversity-aware k-median: Clustering with fair center representation. In Nuria Oliver, Fernando Pérez-Cruz, Stefan Kramer, Jesse Read, and José Antonio Lozano, editors, Machine Learning and Knowledge Discovery in Databases. Research Track - European Conference, ECML PKDD 2021, Bilbao, Spain, September 13-17, 2021, Proceedings, Part II, volume 12976 of Lecture Notes in Computer Science, pages 765–780. Springer, 2021. doi:10.1007/978-3-030-86520-7_47. Ali Vakilian and Mustafa Yalçiner. Improved approximation algorithms for individually fair clustering. In Gustau Camps-Valls, Francisco J. R. Ruiz, and Isabel Valera, editors, Proceedings of The 25th International Conference on Artificial Intelligence and Statistics (AISTATS 2022), 28-30 March 2022, Virtual Event, volume 151 of Proceedings of Machine Learning Research, pages 8758–8779. PMLR, 2022. URL: https://proceedings.mlr.press/v151/vakilian22a. html. Xiaoliang Wu, Qilong Feng, Junyu Huang, and Jianxin Wang. Parameterized approximation algorithm for doubly constrained fair clustering. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2025, Montreal, Canada, August 16-22, 2025, pages 592–600. ijcai.org, 2025. doi:10.24963/ijcai.2025/67. Xiaoliang Wu, Ting Liang, Junyu Huang, and Qilong Feng. Learning-augmented approximation algorithms for group fair k-center clustering. Frontiers of Computer Science, 20:2010408, 2026. doi:10.1007/s11704-025-50627-2. Lunhao Zhang, Pengzhi Gao, and Peng Zhang. Doubly constrained fair clustering for general p-norms. In Fedor V. Fomin and Mingyu Xiao, editors, Computing and Combinatorics - 31st

Constant-Factor Approximations for Doubly Constrained Fair k-Clustering

International Computing and Combinatorics Conference, COCOON 2025, Chengdu, China, August 15-17, 2025, Proceedings, Part I, volume 15983 of Lecture Notes in Computer Science, pages 93–105. Springer, 2025. doi:10.1007/978-981-95-0215-8_8. Zhen Zhang, Xiaohong Chen, Limei Liu, Jie Chen, Junyu Huang, and Qilong Feng. Parameterized approximation schemes for fair-range clustering. 2024. URL: http://papers.nips.cc/paper_files/paper/2024/hash/ 6ee0ebd0983f0926496b7d4e0d48b8e3-Abstract-Conference.html. Ao Zhao, Yang Zhou, and Qian Liu. Improved approximation algorithms for matroid and knapsack means problems. International Journal of Foundations of Computer Science, 36(05):709–729, 2025. arXiv:https://doi.org/10.1142/S012905412246008X, doi: 10.1142/S012905412246008X.

APPENDIX

Omitted proofs from Section 2

▶ Lemma 7. Let (C, φ) be a feasible k-center clustering satisfying GF with objective value λC . Then, (x, y) defined by ( ( 1 if i = φ(j) 1 if i ∈ C xij = and yi = 0 otherwise 0 otherwise is a feasible solution for LP(λC ). Proof. (LP-1.7) holds by definition. Let j ∈ P . As the assignment φ : P → C is a function, there exists exactly one i′ ∈ C such that φ(j) = i. By definition of x, this i′ is the only P element in P such that xi′ j > 0. Hence, i∈P xij = xi′ j = 1, which implies (LP-1.1). To prove (LP-1.2), we observe that xij = 1 if and only if i = φ(j), which is only possible if i ∈ C by definition of φ. For i ∈ C, it is yi = 1 by definition. For xij = 0 the constraint is trivially fulfilled. It is yi = 1 for at most k points i as | C | ≤ k. This implies (LP-1.3). P P P Let i ∈ P and h ∈ H. Then, j∈P xij = j∈P 1[i = φ(j)] = |φ−1 (i)| and j∈Ph xij = P −1 (i) ∩ Ph |. By GF, it follows that |φ−1 (i) ∩ Ph | ≥ ℓh |φ−1 (i)| and j∈Ph 1[i = φ(j)] = |φ −1 −1 |φ (i) ∩ Ph | ≤ uh |φ (i)|. This yields (LP-1.4) and (LP-1.5). (LP-1.6) holds as otherwise, there would be i, j ∈ P with d(i, j) > λC and i = φ(j). This would contradict the objective value of (C, φ). ◀ ▶ Lemma 8. Let (x, y) be a feasible integral solution for LP(λ). Then, (C, φ) defined by C = {i ∈ P | yi = 1}

and

for all j ∈ P

φ(j) = arg max xij i∈P

is a feasible k-center clustering satisfying group fairness with objective value λ. Proof. The LP-constraint (LP-1.1) together with the assumption that x is integral implies that there exists exactly one i ∈ P such that xij = 1 for all j ∈ P . This means that for every j ∈ P , there exists exactly one i ∈ P such that φ(j) = i and therefore the assignment φ is well-defined. By (LP-1.3) and integrality of y, it follows that there are at most k points i ∈ P P such that yi = 1 and therefore | C | ≤ k. For h ∈ H and i ∈ P , it is j∈P xij = |φ−1 (i)| and P −1 ∩ Ph |. Hence, (LP-1.4) and (LP-1.5) immediately imply group fairness. j∈Ph xij = |φ The objective value follows directly from (LP-1.6). ◀ ▶ Lemma 10. Let (x, y) be a feasible solution for LP(λ) and let (x′ , y ′ ) be the solution achieved through the rerouting described above. Then the following properties hold: 1. (x′ , y ′ ) is a feasible solution to LP((γ center +1)λ) P ′ 2. j∈P xij ≥ 1 for all i ∈ CDS 3. y ′ is integral. Proof. 1. For (LP-1.1), consider j ∈ P .  X X X  P x′ij = i∈CDS

i∈CDS

p∈N (i)

 xpi ℓ∈CDS : p∈N (ℓ) xpℓ

xpj +

P X p∈N (CDS )

xpj +

ℓ∈CDS : p∈N (ℓ) xpℓ

X p∈P \N (CDS )

xpj =

X p∈P

xpj 

p∈θ −1 (i)

xpi

p∈N (CDS ) i∈CDS : p∈N (i)

xpj +

xpj = 1,

i∈CDS p∈θ −1 (i)

xpj

Constant-Factor Approximations for Doubly Constrained Fair k-Clustering

where the last equality holds because (x, y) is a feasible solution for the LP and the second-to-last equality holds because θ is a function defined on P \ N (CDS ). By construction, 0 ≤ yi′ ≤ 1 immediately holds for all i ∈ P . Since the values of x are non-negative, x′ij ≥ 0 for all i, j ∈ P as well. By (LP-1.1), it therefore follows that x′ij ≤ 1 for all i, j ∈ P . This implies (LP-1.7). (LP-1.2) holds since either yi′ = 1 and x′ij ≤ 1 by (LP-1.7), or yi′ = 0 and x′ij = 0 for all i, j ∈ P . (LP-1.3) follows since | CDS | ≤ k and yi = 1 if and only if i ∈ CDS . For (LP-1.4), fix i ∈ CDS and h ∈ H. Then,   X X X X x pi  P xpj + xpj  x′ij = xpℓ ℓ∈C : p∈N (ℓ) −1 DS j∈Ph j∈Ph p∈N (i) p∈θ (i)   X X X X xpi P = xpj  + xpj ℓ∈CDS : p∈N (ℓ) xpℓ j∈Ph p∈N (i) p∈θ −1 (i) j∈Ph   X X X X xpi P ≤ uh xpj  + uh xpj ℓ∈CDS : p∈N (ℓ) xpℓ j∈P p∈N (i) p∈θ −1 (i) j∈P   X X X xpi  P xpj + xpj  = uh xpℓ ℓ∈C : p∈N (ℓ) −1 DS j∈P p∈N (i) p∈θ (i) X ′ = uh xij j∈P

(LP-1.5) follows analogously. For (LP-1.6), consider i, j ∈ P such that x′ij > 0. By definition of x′ , it must be that P xpi i ∈ CDS . Also by definition, one of the summands p∈N (i) P x or xpℓ pj ℓ∈CDS : p∈N (ℓ) P P x pi P xpj > 0, then there exists p∈θ −1 (i) xpj must be > 0. If p∈N (i) x ℓ∈CDS : p∈N (ℓ)

pℓ

p ∈ N (i) such that xpi > 0 and xpj > 0. As (x, y) is a feasible solution for LP(λ), (LP-1.6) implies d(p, i) ≤ λ and d(p, j) ≤ λ. Hence, by triangle inequality, d(i, j) ≤ 2λ. P −1 If (i) such that xpj > 0. Again, by p∈θ −1 (i) xpj > 0, then there exists p ∈ θ (LP-1.6), d(p, j) ≤ λ. Further, as θ(p) = i, it follows that i ∈ argmini′ ∈CDS d(p, i′ ). By definition of λ, it is d(p, i) = mini′ ∈CDS d(p, i′ ) ≤ γ ·λ. Plugging everything together yields d(i, j) ≤ d(i, p) + d(p, j) ≤ (γ center +1)λ. 2. Let i ∈ CDS . Then,   X X X X xpi  P xpj + xpj  x′ij = ℓ∈CDS : p∈N (ℓ) xpℓ j∈P j∈P p∈N (i) p∈θ −1 (i) X X xpi P ≥ xpj ℓ∈CDS : p∈N (ℓ) xpℓ j∈P p∈N (i) X X xpi P = xpj , ℓ∈CDS : p∈N (ℓ) xpℓ p∈N (i)

j∈P

where the first inequality holds because (x, y) is a feasible solution for LP(λ) and therefore P satisfies xij ≥ 0 for all i, j ∈ P (LP-1.7). Further, we can argue that j∈P xpj ≥ P x for all p ∈ N (i) as all summands are non-negative and we sum over a j∈CDS : p∈N (j) pj

APPENDIX

subset of the summands. Using this bound, the numerator and the denominator cancel P P out, and we remain with j∈P x′ij ≥ p∈N (i) xpi . Because xpi = 0 if and only if p ̸∈ N (i), P P we can deduce that p∈N (i) xpi = p∈P xpi = 1 using (LP-1.1). 3. For all i ∈ P , yi ∈ {0, 1} by definition. ◀ ▶ Lemma 11 (Group fairness – k-center). For each center i and each color h it holds that X X X lh x′′ij − 2 ≤ x′′ij ≤ uh x′′ij + 2. j∈P

j∈Ph

j∈P

P Proof. Let massh (i, x′ ) = j∈Ph x′ij and mass(i, x′ ) = j∈P x′ij be the sum of points of color h that is assigned to center i and the sum of total points assigned to center i after the rerouting step respectively. As (x′ , y ′ ) is a feasible solution for LP(λ) (see Lemma 10), P we know that lh · mass(i, x′ ) ≤ massh (i, x′ ) ≤ uh · mass(i, x′ ). Let massh (i, x′′ ) = j∈Ph x′′ij P and mass(i, x′′ ) = j ∈ P x′′ij be the sum of points (of color h) that is assigned to center i in in the final point assignment step (see Section 2.4). We know that ⌊massh (i, x′ )⌋ ≤ massh (i, x′′ ) ≤ ⌈massh (i, x′ )⌉ because the lower and upper bounds on each edge ((i, h), i) ∈ P P A3 are ⌊ j∈Ph x′ij ⌋ and ⌈ j∈Ph x′ij ⌉. Due to the lower and upper bounds on each edge P P (i, t) ∈ A4 , which are ⌊ j∈P x′ij ⌋ and ⌈ j∈P x′ij ⌉, we additionally know that ⌊mass(i, x′ )⌋ ≤ mass(i, x′′ ) ≤ ⌈mass(i, x′ )⌉. Since ⌈massh (i, x′ )⌉ < massh (i, x′ ) + 1 and ⌊massh (i, x′ )⌋ > massh (i, x′ ) − 1, it is true that massh (i, x′′ ) < massh (i, x′ ) + 1 ≤ uh · mass(i, x′ ) + 1 ≤ uh · (mass(i, x′′ ) + 1) + 1 = uh · mass(i, x′′ ) + uh + 1 ≤ uh · mass(i, x′′ ) + 2 and massh (i, x′′ ) > massh (i, x′ ) − 1 ≥ lh · (mass(i, x′′ ) − 1) − 1 = lh · mass(i, x′ ) − lh − 1 ≥ lh mass(i, x′′ ) − 2. ◀ P

▶ Theorem 3. Let γ center be the approximation factor of a given approximation algorithm for DS-fair k-center. There exists an algorithm that computes a (γ center +1)-approximation with GF-violation of ≤ 2 for the doubly constrained fair k-center problem in polynomial time. Proof. As it follows from Lemmas 8, 10 and 11 that the returned solution of Algorithm 1 has cost of at most 4 · OPT and satisfies DS exactly and GF with an additive violation of at most 2, all that is left to show is the polynomial running time. Assume that we are given an algorithm Acenter for the center constraint with running time tcenter and can solve an LP in tLP time. If using the DS k-center algorithm by Jones et al. [22] as Acenter , computing a set of diverse centers takes O(nk) time. To find a good upper bound λ for the clustering cost, we iterate over the set of pairwise distances in P and compute an LP solution in time O(n2 tLP ). Solving LP (λ) takes tLP time. Rerouting one point requires iterating over all centers for each neighbor of each center i ∈ CDS as well as iterating over points not neighboring a center, taking O(k 2 n) time per point. Computing the final assignment first requires building the flow network by iterating over P , CDS ×H, CDS , and P × H, requiring O(nm + km) time. Computing the max flow of this network can be done in polynomial time, e. g., using the algorithm by Orlin [28] taking O(V E) time on our network, where V ∈ O(n + km + k) and E ∈ O(n + nmk + mk + k). Lastly, computing the final assignment takes O(n2 ) time. In total this results in polynomial running time in O(tcenter + n2 tLP + k 2 m2 n + kmn2 ). ◀

Omitted proofs from Section 3

▶ Lemma 12. (x′ , y ′ ) is a feasible solution to the LP in Section 3.2. It holds for all i ∈ CDS . All yi′ in this solution are integral.

′ j∈P xij ≥ 1

Constant-Factor Approximations for Doubly Constrained Fair k-Clustering

Proof. We first prove the feasibility: To show Equation (LP-2.1) we consider the following: Let j ∈ P . Then   X X X ′ X X  rpl ) · xpj  rpi · xpj + (1 − x′ij = i∈CDS

i∈CDS

p∈N (i)

p∈θ −1 (i)

rpi · xpj +

xpj −

i∈CDS p∈N (i)

i∈CDS p∈θ −1 (i)

i∈CDS p∈θ −1 (i) l′ ∈CDS

rpl · xpj

rpi · xpj +

i∈CDS p∈N (i)

p∈P

rpi · xpj +

xpj −

X X

′

rpl · xpj

′

p∈P l′ ∈CDS

xpj −

′

rpl · xpj

l′ ∈CDS p∈N (l′ )

p∈P

i∈CDS p∈N (i)

l′ ∈CDS

xpj = 1

p∈P

Equation (LP-2.2) holds automatically since either yi′ = 1 and x′ij ≤ 1 by Equation (LP-2.1) or yi′ = 0 and x′ij = 0 for all i, j Equation (LP-2.3) follows since | CDS | ≤ k and yi = 1 if and only if i ∈ CDS . to show Equation (LP-2.4) we fix i ∈ CDS , h ∈ H. Then it holds: X x′ij j∈P h

 = =

 X

rpi · xpj +

 p∈N (i)

rpi ·

X j∈P

p∈N (i)

′

(1 −

xpj + αh

rpl ) · xpj 

l′ ∈CDS :p∈N (l′ )

p∈θ −1 (i)

j∈P h

p∈N (i)

≤ αh

xpj +

′

(1 −

p∈θ −1 (i)

j∈P h

rpi ·

rpl ) ·

l′ ∈CDS :p∈N (l′ )

j∈P h

rpl ) ·

(1 −

′

p∈θ −1 (i)

l′ ∈CDS :p∈N (l′ )

X 

= αh

xpj



X j∈P

 = αh

xpj

rpi · xpj +

(1 −

p∈θ −1 (i)

p∈N (i)

′

rpl ) · xpj 

l′ ∈CDS :p∈N (l′ )

x′ij

j∈P

Equation (LP-2.5) works analogously to Equation (LP-2.4). P We now only have to show j∈P x′ij ≥ 1 for all i ∈ CDS . X j∈P

xpi

x′ij ≥

P p∈N (i)

l∈P xpl

xpj

j∈P

xpi

p∈N (i)

=1 ◀ ▶ Lemma 13 (Cost k-median). For the k-median cost of (x′ , y ′ ) the following holds: cost(x′ , y ′ ) ≤ 3 · cost(x, y) + cost(xDS , y DS ).

APPENDIX

Proof. In the following, we will bound the cost of the resulting solution. For better readability, we divide the assignment function into two parts: x′N which describes the part of the assignments that centers get assigned from the mass which their neighbors receive in (x, y). More formal X

x′N ij =

rpi · xpj

p∈N (i)

x′θ which describes the remaining assignments via the nearest neighbor function θ which leads to X

x′θ ij =

(1 −

′

rpl )xpj

l′ ∈CDS

p∈θ −1 (i)

For an illustration, we defer to Figure 3 which shows x′N via the blue arrows and x′θ ′Θ via the red arrows. It is easy to see that it holds x′ij = x′N ij + xij . Therefore we know ′ ′ ′N ′ ′Θ ′ cost(x , y ) =cost(x , y )+cost(x , y ). We first bound the cost of (x′N , y ′ ). By repeated application of the triangle inequality, we get:

X X

cost(x′N , y ′ ) =

x′N ij d(i, j)

(1)

i∈CDS j∈P

 =

 X

rpi ·

 i∈CDS

p∈N (i)

j∈P

xpi

xpj d(i, j)

(2)

 ≤



 i∈CDS

l∈P xpl

p∈N (i)

xpj (d(p, j) + d(p, i))

 =

 X

xpi d(p, i) + P

 i∈CDS

(3)

j∈P

l∈P xpl

p∈N (i)

≤ cost(x, y) +

xpi

X P

i∈CDS p∈N (i)

= cost(x, y) +

xpi

i∈CDS p∈N (i)

l∈P xpl

rpi ·

xpj d(p, j)

(4)

j∈P

xpj d(p, j)

(5)

j∈P

xpj d(p, j)

(6)

j∈P

(7)

We can bound the cost of (x′θ , y ′ ) the following way: Let j ∈ P, i ∈ CDS and let φ (j) = argminx∈CDS d(x, j) be the center j is assigned to in the center fair solution (xDS , y DS ). Then repeatedly using the triangle inequality and the definition of θ leads to: DS

Constant-Factor Approximations for Doubly Constrained Fair k-Clustering

x′θ ij d(i, j) X X ′ rpl ) · xpj d(i, j) = (1 − ≤

p∈θ −1 (i)

l′ ∈CDS

(1 −

(8) (9)

′

rpl ) · xpj (d(p, j) + d(p, i))

(10)

l′ ∈CDS

p∈θ −1 (i)

! =

xpj (d(p, j) + d(p, i)) −

(11)

l′ ∈CDS

p∈θ −1 (i)

≤

′ rpl · xpj (d(p, j) + d(p, i))

xpj (2d(p, j) + d(φDS (j), j)) −

′

rpl · xpj d(p, j)

(12)

p∈θ −1 (i) l′ ∈CDS

p∈θ −1 (i)

When we sum up over all centers and points this leads to the following bound: X X cost(x′θ , y ′ ) = x′θ ij d(i, j)

(13)

i∈CDS j∈P

 ≤

X X

 X

 i∈CDS j∈P

xpj (2d(p, j) + d(φ

(j), j)) −

′ rpl · xpj d(p, j)

(14)

p∈θ −1 (i) l′ ∈CDS

p∈θ −1 (i)

≤ 2cost(x, y) + cost(xDS , y DS ) −

X X

′

rpl · xpj d(p, j)

(15)

i∈CDS j∈P p∈θ −1 (i) l′ ∈CDS

= 2cost(x, y) + cost(xDS , y DS ) −

′

rpl · xpj d(p, j)

(16)

j∈P p∈θ −1 [CDS ] l′ ∈CDS

= 2cost(x, y) + cost(xDS , y DS ) −

X X

′

rpl · xpj d(p, j)

(17)

j∈P l′ ∈CDS p∈N (l′ )

Therefore by combining our bounds for cost(x′N , y ′ ) and cost(x′Θ , y ′ ) we get ′ ′θ ′ cost(x′ij , y ′ ) = cost(x′N ij , y ) + cost(xij , y ) X X X rpi · xpj d(p, j) + 2cost(x, y) ≤ cost(x, y) + i∈CDS p∈N (i)

+ cost(xDS , y DS ) −

(18) (19)

j∈P

X X

′

rpl · xpj d(p, j)

(20)

j∈P l′ ∈CDS p∈N (l′ )

= 3cost(x, y) + cost(xDS , y DS ) which concludes the proof.

(21) ◀

▶ Lemma 14 (Cost k-means). For the k-means cost of (x′ , y ′ ) the following holds for p, q > 0: cost2 (x′ , y ′ ) ≤ (1 + p2 + (1 +

1 1 1 )(2 + q 2 )) cost2 (x, y) + (1 + 2 )(1 + 2 ) cost2 (xDS , y DS ). p2 p q

Proof. The analysis of the cost of the k-means cost function works analogously to the analysis of the k-median objective. The main difference is that we cannot simply use the triangle inequality because the distances are squared. Therefore we will be using the more general version (a + b)2 ≤ (1 + p2 ) · a2 + (1 + p12 ) · b2 for p > 0. In the following (x′N , y ′ ) and (x′θ , y ′ ) are defined as in the proof of the previous Lemma 13.

APPENDIX

Again, we start by bounding the cost of (x′N , y ′ ): X X

cost(x′N , y ′ ) =

2 x′N ij d(i, j)

(22)

i∈CDS j∈P

rpi ·

xpj d(i, j)2

(23)

j∈P

i∈CDS p∈N (i)





1 )d(p, j)2 + (1 + p21 )d(p, i)2 ) p21 j∈P i∈CDS p∈N (i)   X X X 1  (1 + 2 )xpi d(p, i)2 + rpi · (1 + p21 )xpj d(p, j)2  = p1

≤

rpi ·



i∈CDS

≤ (1 +

xpj · ((1 +

(24)

(25)

j∈P

p∈N (i)

X 1 )cost(x, y) + 2 p1

rpi ·

(1 + p21 )xpj d(p, j)2

(26)

j∈P

i∈CDS p∈N (i)

for p1 ∈ R>0 . We can bound the cost of (x′θ , y ′ ) the following way: Let j ∈ P, i ∈ CDS and let φ (j) = argminx∈CDS d(x, j) be the center j is assigned to in the center fair solution (xDS , y DS ). DS

2 x′θ ij d(i, j) =

(1 −

p∈θ −1 (i)

rpl )xpj · (1 + p22 )d(p, j)2 + ((1 +

l′ ∈CDS

xpj ((1 + p22 )d(p, j)2 + (1 +

p∈θ −1 (i)

≤−

′

rpl xpj ((1 + p22 )d(p, j)2 + (1 +

xpj (1 + p22 )d(p, j)2 + ((1 +

p∈θ −1 (i)

1 )d(p, i)2 ) p22

(28)

1 )d(p, i)2 ) p22

p∈θ −1 (i) l′ ∈CDS

≤

(27)

′

(1 −

′

rpl )xpj d(i, j)2

l′ ∈CDS

p∈θ −1 (i)

≤

(29)

1 )d(p, i)2 ) p22

1 )d(p, i)2 ) − p22

(30) X

′

rpl xpj (1 + p22 )d(p, j)2

p∈θ −1 (i) l′ ∈CDS

(31) 1 1 ≤ xpj (1 + p22 )d(p, j)2 + ((1 + 2 )((1 + 2 )d(φDS (j), j)2 + (1 + q 2 )d(p, j)2 ) (32) p2 q p∈θ −1 (i) X X ′ ≤− rpl xpj (1 + p22 )d(p, j)2 (33) X

p∈θ −1 (i) l′ ∈CDS

(1 + p22 + (1 +

p∈θ −1 (i)

1 1 1 )(1 + q 2 ))xpj d(p, j)2 + ((1 + 2 )(1 + 2 ))xpj d(φDS (j), j)2 p22 p2 q (34)

≤−

p∈θ −1 (i) l′ ∈C

for p2 , q > 0.

′

rpl xpj (1 + p22 )d(p, j)2

(35)

Constant-Factor Approximations for Doubly Constrained Fair k-Clustering

If we take the sum over all centers i ∈ CDS and points j ∈ P we get X X 2 cost(x′θ , y ′ ) = x′θ ij d(i, j)

(36)

i∈CDS j∈P

1 = 1 + p22 + (1 + 2 )(1 + q 2 ))xpj d(p, j)2 p2 i∈CDS j∈P p∈θ −1 (i) 1 1 + (1 + 2 )(1 + 2 )xpj d(φDS (j), j)2 ) p q X 2X X X ′ rpl xpj (1 + p22 )d(p, j)2 ≤− X X

(37) (38) (39)

i∈CDS j∈P p∈θ −1 (i) l′ ∈CDS

1 1 1 ≤ (1 + p22 + (1 + 2 )(1 + q 2 ))cost(x, y) + (1 + 2 )(1 + 2 )cost(xDS , y DS ) p2 p2 q X X X X ′ rpl xpj (1 + p22 )d(p, j)2 ≤−

(40) (41)

i∈CDS j∈P p∈θ −1 (i) l′ ∈CDS

1 1 1 ≤ (1 + p22 + (1 + 2 )(1 + q 2 ))cost(x, y) + (1 + 2 )(1 + 2 )cost(xDS , y DS ) p2 p2 q X X X ′ rpl xpj (1 + p22 )d(p, j)2 ≤−

(42) (43)

p∈CDS j∈P l′ ∈CDS

for p2 , q ∈ R>0 . Therefore if we combine the bounds for cost(x′N , y ′ ) and cost(x′Θ , y ′ ) and set p1 = p2 = p we get ′ ′θ ′ cost(x′ij , y ′ ) = cost(x′N ij , y ) + cost(xij , y ) X X X 1 ≤ (1 + 2 )cost(x, y) + rpi · (1 + p2 )xpj d(p, j)2 p i∈CDS p∈N (i)

(44) (45)

j∈P

1 1 1 ≤ + (1 + p2 + (1 + 2 )(1 + q 2 ))cost(x, y) + (1 + 2 )(1 + 2 )cost(xDS , y DS ) p p q X X X ′ rpl xpj (1 + p2 )d(p, j)2 ≤−

(46) (47)

p∈CDS j∈P l′ ∈CDS

= (1 + p2 + (1 +

1 1 1 )(2 + q 2 ))cost(x, y) + (1 + 2 )(1 + 2 )cost(xDS , y DS ) p2 p q

for p, q > 0. This concludes the proof.

(48) ◀

▶ Lemma 15 (Group fairness – k-median, k-means). For each center i and each color h it holds that X X X lh x′′ij − 2 ≤ x′′ij ≤ uh x′′ij + 2. j∈P

j∈Ph

j∈P

Proof. First, we remember that by Lemma 12 (x′ , y ′ ) was a fractional solution satisfying P group fairness. To make notation a bit easier, we denote by massh (i, x) = j∈P h xij the amount of color h points that get assigned to center i in the solution (x, y). Analogously let P mass(i, x) = j∈P xij be the total amount of points assigned to center i in (x, y). It is easy to check that the following hold: ⌊massh (i, x′ )⌋ ≤ massh (i, x′′ ) ≤ ⌈massh (i, x′ )⌉ by the balance of (i, h) and the fact that the outgoing edge only has capacity 1 ⌊mass(i, x′ )⌋ ≤ mass(i, x′′ ) ≤ ⌈mass(i, x′ )⌉ by the balance of i and the fact that the outgoing edge only has capacity 1

APPENDIX

Therefore we know massh (i, x′′ ) ≤ massh (i, x′ ) + 1 ≤ uh · mass(i, x′ ) + 1 ≤ uh (mass(i, x′′ ) + 1) + 1 = uh · mass(i, x′′ ) + uh + 1 ≤ uh · mass(i, x′′ ) + 2 and analogously massh (i, x′′ ) ≥ massh (i, x′ ) − 1 ≥ lh · mass(i, x′ ) − 1 ≥ lh (mass(i, x′′ ) − 1) − 1 = lh · mass(i, x′′ ) − lh − 1 ≥ lh · mass(i, x′′ ) − 2 This shows that there is an additive violation of at most 2 for the (GF) constraint.

◀

▶ Theorem 5. There exists a polynomial time algorithm that computes a (γ med +3)-approximation with GF-violation of at most 2 for the doubly constrained fair k-median problem, where γ med is the approximation factor of a given approximation algorithm for DS-fair k-median. q √ ( 1 + ( γ means + 1)2 + 1)2 -approximation with GF-violation of at most 2 for the doubly constrained fair k-means problem, where γ means is the approximation factor of a given approximation algorithm for DS-fair k-means. Proof. To see that (x′′ , y ′ ) satisfies the center fairness constraint, we recall that CDS fulfilled the center fairness constraint. Since we never opened or changed any centers in CDS , we only have to show that every i ∈ CDS gets assigned at least one point in (x′′ , y ′ ). Let i ∈ CDS . P From Lemma 12 we know that j∈P x′ij ≥ 1, and therefore either there exists an h ∈ H with P P ′ ′ j∈P h xij ≥ 1 or j∈P h xij < 1 for all h ∈ H. In the first case we know that the balance of the point (i, h) is smaller or equal to −1, which means that at least one point has to send (integral) flow in (x′′ , y ′ ) to it, which means there is at least one point assigned to i. If P P P P ′ ′ ′ j∈P h xij < 1 for all h ∈ H, then we know that −(⌊ j∈P xij ⌋ − h∈H ⌊ j∈Ph xij ⌋) ≤ −1 and therefore the vertex corresponding to i gets integral flow from at least 1 point in the solution, meaning that at least one point is assigned to i. Thus our solution satisfies center fairness. The group fairness follows directly from Lemma 15. For the cost bound, we see that (x′ , y ′ ) can be translated into a valid solution for the min cost flow with the same cost, and therefore the cost of (x’, y’) is an upper bound for the cost of (x′′ , y ′ ) for both objective functions. The cost bound for k-median follows now directly from Lemma 13 and the fact that both cost(x, y) and γ 1 cost(xDS , y DS ) are lower med bounds for the cost of the optimal doubly fair solution, since this optimal solution has to be both, group q fair and center fair. The bound for the k-means cost follows analogously if we √ √ 2 set p = 1 + (1 + γ means )2 and q 2 = γ means . The running time analysis is very similar to the k-center case. Computing a set of centers with the desired center based constrained is dependent on the chosen approximation algorithm. Both the algorithms we discussed in combination with the reduction by Thejaswi et al. [32], the matroid median algorithm by Krishnaswamy et al. [24] for DS-fair k-median, and the matroid means algorithm by Zhao et al. [38] for DS-fair k-means have polynomial running times. Finding an upper bound on the clustering cost and rerouting the points to centers fulfilling the center-based constraint does not take the same time as in the k-center case. The main difference here is solving a min-cost flow instead of a max flow, which can also be computed in polynomial time, e. g., using the algorithm by Chen et al. [9]. The total running time is polynomial for both k-median and k-means. This concludes the proof of the theorem. ◀

Constant-Factor Approximations for Doubly Constrained Fair k-Clustering

Notation (P, d) C C1 , . . . , C k H m = |H| Ph φ: P → C ℓh , uh Lh , Uh

general metric space with point set P set of centers clusters set of colors number of colors sets of points with color h for h ∈ {1, . . . , m} assignment of points to centers lower and upper bound for color h in the group fairness definition lower and upper bound for color h in the definition of diverse center selection CDS center set of the DS-fair solution (x, y) solution of the group fairness LP (x′ , y ′ ) solution after the rerouting step (x′′ , y ′′ ) final, integral doubly fair solution xij the amount of mass sent from point j to point i yi the extent to which point i is opened (used as a center) γ center , γ med , γ means currently best approximation factor to the (DS) variant of the resp. objective mass(i, x) sum over all xij massh (i, x) sum over all xij where j has color h rpi ratio of xpi on mass(i, x) Table 2 Notation used throughout the paper

Record · ID 31280 · SHA-256 187b7bf295298db6
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.