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

Let $(P,d)$ be a general metric space with $|P|=n$ and $k\in \{1,\mathrm{\dots },n\}$ an integer. A $k$-clustering is a partition of $P$ into $k$ clusters $C_1,\mathrm{\dots },C_k$ optimizing some objective function. We are considering center-based objectives, where a clustering is induced by a set of centers $𝒞\subseteq P$ with $|𝒞|\le k$ and an assignment $\phi :P\to 𝒞$ 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={\phi }^{-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 ${\max }_{p\in P}d(p,\phi (p))$ among the clusters. In $k$-median, the objective is to minimize the sum of distances of points to their assigned center, i. e., ${\sum }_{p\in P}d(p,\phi (p))$, and in $k$-means it is the sum of squared distances of points to centers that we want to minimize, i. e., ${\sum }_{p\in P}d{(p,\phi (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\le h\le m$, we denote the group of points of color $h$ by $P_h$. We assume that every point in $P$ is assigned exactly one color $1\le h\le m$, i.e., $P=P_1\dot{\cup }\mathrm{\dots }\dot{\cup }{P}_m$. 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 ${\mathrm{\ell }}_h$ and an upper bound $u_h$ on these fractions. To relax this problem, we further allow a small additive violation of these fractional bounds.

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.

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 $L_h=U_h$ for all $h\in 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.

We have two main results; the first is a constant factor approximation algorithm for the doubly constrained fair $k$-center problem.

Using the currently best approximation factor of $3$ for $k$-center with DS by Jones, Nguyen and Nguyen [21], this yields a $4$-approximation.

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.

Currently the best algorithm for center fair $k$-median computes a $7.081$-approximation [29, 23] and for $k$-means a $256$-approximation [29, 30], resulting in the following:

For the special case of doubly constrained fair $k$-means under euclidean distance we can use the $64$-approximation [29, 35] to achieve an $83+2\sqrt{82}\approx 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-box¹¹1https://www.acm.org/diversity-inclusion/words-matter 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 [27, 35] or the notion of individual fairness [22, 30].

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 [10], bounded representation [2], and colorful clustering [20]. Other fairness concepts focus on distances, like individual fairness [24] and socially fair clustering [1].

Chierichetti, Kumar, Lattanzi and Vassilvitskii [10] 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 a deterministic $3$-approximation algorithm with additive violation of at most $1$ [4] and randomized $3$-approximation with no additive violation in expectation [18]. 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 [11]. For $k$-means, a $5+4\sqrt{2}+ϵ\approx 10.66$-approximation with violation of $\le 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, 18]. Further related for group fairness include the integration of privacy constraints [26], the learning-augmented setting [32], 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 [21], and a $3$-approximation 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 [25]. If color groups are non-disjoint, the problem is inapproximable to any factor, assuming $P\ne NP$ [29]. For the most general version of diverse center selection, there exists an FPT $3$-approximation that can even handle outliers [14]. For $k$-median and $k$-means, a result for general $p$-norm objectives implies $e^{O(1)}$-approximations for general diverse center selection. In the exact case, Thejaswi, Ordozgoiti and Gionis [29] 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 [23, 30]; where the $k$-means variant allows for a $64$-approximation if the distances are Euclidean [29, 35]. In the FPT-regime, randomized $(1+\frac{2}{e}+ϵ)$- and $(1+\frac{8}{e}+ϵ)$-approximations for general diversity-aware $k$-median and $k$-means can be achieved, respectively [28]. For Euclidean spaces, $(1+ϵ)$-approximations are possible for both objectives under the diverse center selection constraint [34]. Further related work in the realm of diverse center selection includes distributed models [6] and the streaming setting [6, 16].

For doubly constrained fair clustering, the landscape of related work is sparser. Only for $k$-center, there exists a constant-factor approximation algorithm [13]. For $k$-median, there is an FPT-time approximation algorithm by [31] 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 [33] that achieves an approximation ratio of $O({\mathrm{\Delta }}^{1/p})$ with an additive violation of at most $5$, where $\mathrm{\Delta }$ 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.081$-approximation for matroid median [23], and a $256$-approximation for matroid means [30], which is improved to $64$ in Euclidean spaces [35]. For knapsack constraints, the factors are $3$ [19], $6.387+ϵ$ [17] and $1128+ϵ$ [35] for $k$-center, $k$-median and (Euclidean) $k$-means.

To guarantee our solution fulfills the DS constraint we use an existing algorithm for diversity-aware $k$-center as an opaque-box algorithm. In the following, let ${𝒞}_{\text{DS}}$ be the returned set of centers that satisfy the DS constraint, and ${\gamma }_{\text{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. [21] with $O(nk)$ running time. If the combination of group fairness with another constraint is desired, a corresponding approximation algorithm can be used instead.

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., $x_{ij}$ denotes the amount of mass sent from point $j\in P$ to point $i\in 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 $y_i$ can be interpreted as the amount to which $i\in P$ is opened as a center.

We denote the linear program by $\text{LP}(\lambda )$. 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 $\lambda$ away. Combining this with a search over all possible values of $\lambda$ 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 $\text{LP}(\lambda )$ when $\lambda$ is at least the objective value of the clustering. The proof of the following two lemmas can be found in the full version.

We choose the value of $\lambda$ as follows. It should be large enough such that $\text{LP}(\lambda )$ allows for a feasible solution. For this, let ${\lambda }^{\text{LP}}$ denote the minimal value such that $\text{LP}({\lambda }^{\text{LP}})$ has a solution. Further, $\lambda$ should be large enough such that the ${\gamma }_{\text{center}}$-approximation for $k$-center with DS has cost upper bounded by ${\gamma }_{\text{center}}\cdot \lambda$. For this, let ${\lambda }^{\text{DS}}$ be minimal such that the ${\gamma }_{\text{center}}$-approximation returns a solution with exactly $k$ centers and value of at most ${\gamma }_{\text{center}}\cdot {\lambda }^{\text{DS}}$. Now, we set $\lambda ≔\max \{{\lambda }^{\text{LP}},{\lambda }^{\text{DS}}\}$. We can upper bound the value of $\lambda$ by the value of an optimal solution satisfying both GF and DS.

Let $(x,y)$ be the (fractional) group fair solution computed by solving the LP optimally, and ${𝒞}_{\text{DS}}$ be the set of diverse centers computed by a ${\gamma }_{\text{center}}$-approximation for $k$-center with DS constraint. If $x_{ij}>0$ for some $j\in P$, the point $i$ can be considered as a center in this solution. We want to reroute mass to the centers in ${𝒞}_{\text{DS}}$, such that positive mass is only sent to points in ${𝒞}_{\text{DS}}$. Meanwhile, we want to ensure that all centers in ${𝒞}_{\text{DS}}$ get some positive mass. That is, we construct $(x^{\prime },y^{\prime })$ such that $\{i\in P\mid {\sum }_{j\in P}{x}_{ij}^{\prime }>0\}={𝒞}_{\text{DS}}$, 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\in P$, we define the set $N(j)≔\{i\in P\mid x_{ij}>0\}$ of all the points that $j$ sends positive mass to (i. e., is assigned to in the fractional solution). For a set of points $P^{\prime }\subseteq P$, we define $N(P^{\prime })≔{\bigcup }_{j\in P^{\prime }}N(j)$.

The overall idea is to take all the mass incoming at some point $p\in P$ in the LP solution $(x,y)$ and reroute it to a “nearby” center in ${𝒞}_{\text{DS}}$ 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\in P$ that gets some mass in the current solution, i.e., ${\sum }_{j\in P}{x}_{pj}>0$. Depending on $p$’s position relative to the centers in ${𝒞}_{\text{DS}}$, we decide how to reroute the incoming mass at $p$.

We want to prevent any center in ${𝒞}_{\text{DS}}$ from becoming empty (i.e., it gets no mass assigned). By the first constraint of the LP, ${\sum }_{i\in P}{x}_{ij}=1$, every point, particularly every center in ${𝒞}_{\text{DS}}$, must possess some outgoing mass in the LP solution $(x,y)$. That is, for every $c\in {𝒞}_{\text{DS}}$, the set $N(c)$ is non-empty. To ensure that mass is sent to a point $c\in {𝒞}_{\text{DS}}$, we reroute mass sent to a point $p\in N(c)$ to $c$. However, these sets might overlap, and if we sent all incoming mass at $p\in 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\in N({𝒞}_{\text{DS}})$ among all points $c\in {𝒞}_{\text{DS}}$ with $p\in N(c)$. A center $i\in {𝒞}_{\text{DS}}$ gets as much mass from $j\in P$ with $x_{p,j}>0$ as it sends to $p$, proportional to the masses sent from all centers $i^{\prime }\in {𝒞}_{\text{DS}}$ to $p$.

In the remaining case that $p\notin N({𝒞}_{\text{DS}})$, $p$ gets mass solely from points that are not desired centers themselves. In this case, we can safely reroute all mass ${\sum }_{j\in P}{x}_{pj}$ to some nearby center in ${𝒞}_{\text{DS}}$. To keep the distances small, we choose the center $i\in \arg {\min }_{i^{\prime }\in {𝒞}_{\text{DS}}}d(p,i^{\prime })$ that is closest to $p$. Formally, a new fractional solution $(x^{\prime },y^{\prime })$ is defined as follows:

and

where $\theta :P\setminus N({𝒞}_{\text{DS}})\to {𝒞}_{\text{DS}}$ with

Figure 1 schematically visualizes how the mass emitted from a point $j$ is rerouted to centers in ${𝒞}_{\text{DS}}$. We can show that the rerouted solution $(x^{\prime },y^{\prime })$ is a feasible solution to $\text{LP}(({\gamma }_{\text{center}}+1)\lambda )$ such that $y^{\prime }$ is integral. Further, every $c\in {𝒞}_{\text{DS}}$ gets a mass of at least $1$ assigned. We defer the proof to the full version.

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^{\prime }$ 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\}\cup P\cup \{(i,h)\mid i\in {𝒞}_{\text{DS}},h\in H\}\cup {𝒞}_{\text{DS}}$ and $E=A_1\cup A_2\cup A_3\cup A_4$. The set of edges $A_1=\{(s,j)\mid j\in P\}$ connects all points in $P$ to the source. Each point $j\in P$ is connected to a center-color-node $(i,h)$, if $j\in P_h$ and $x_{ij}^{\prime }=1$. More formally $A_2=\{(j,(i,h))\mid i\in {𝒞}_{\text{DS}},j\in P_h,x_{ij}^{\prime }>0\}$. The edges in $A_1$ and $A_2$ have capacity 1. Each of the color-center-nodes $(i,h)$ is connected to its corresponding center $i$, thus $A_3=\{((i,h),i)\mid i\in {𝒞}_{\text{DS}},h\in 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 solution. Since ${\sum }_{j\in P_h}{x}_{ij}^{\prime }$ is not necessarily integral, lower and upper bounds on the edges are introduced; the lower bound is $\lfloor {\sum }_{j\in P_h}{x}_{ij}^{\prime }\rfloor$ and the upper bound is $\lceil {\sum }_{j\in P_h}{x}_{ij}^{\prime }\rceil$. Lastly, the set of edges $A_4=\{(i,t)\mid i\in {𝒞}_{\text{DS}}\}$ 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 in the fractional solution, but again ${\sum }_{j\in P}{x}_{ij}^{\prime }$ is not necessarily integral. Each edge has the lower bound $\lfloor {\sum }_{j\in P}{x}_{ij}^{\prime }\rfloor$ and the upper bound $\lceil {\sum }_{j\in P}{x}_{ij}^{\prime }\rceil$ (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^{\prime }$), there is also an integral flow with value $|P|$. Let $x^{\prime \prime }$ be the integral assignment from the flow. Our final solution is given by the pair $(y^{\prime },x^{\prime \prime })$. This step can introduce an additive violation of 2.

We find a center fair solution $({𝒞}_{\text{DS}},\phi )$ via an opaque-box algorithm for the respective problem. For notation reasons, we can interpret this solution as an integral assignment $(x^{DS},y^{DS})$ with $y_i^{DS}=1$ if and only if $i\in {𝒞}_{\text{DS}}$ and $x_{ij}^{DS}=1$ iff $\phi (j)=i$. Let ${\gamma }_{\text{med}}$ and ${\gamma }_{\text{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. [29] give a reduction to the matroid median problem, allowing a $\rho$-approximation algorithms for the matroid median problem to be used to compute a $\rho$-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. [23].

The reduction by Thejaswi et al. [29] can also be modified to reduce $k$-means with DS to the facility location problem with ${\mathrm{\ell }}_p$-norm cost under matroid constraint, where $p=2$, introduced by Vakilian and Yalçıner [30]. 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 [30] also give a ${16}^p$ approximation for the facility location problem with ${\mathrm{\ell }}_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 can also use the construction by Thejaswi et al. [29] 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. [35].

The following relaxed LP finds a feasible assignment satisfying the GF constraint and minimizes the $k$-median objective function

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.

We use the center set ${𝒞}_{\text{DS}}$ from Section 3.1 and reroute the point assignments of $(x^{LP},y^{LP})$ in a way that the following hold:

• $\mathrm{■}$

  the resulting solution ($x^{\prime },y^{\prime }$) is a feasible solution to the LP

• $\mathrm{■}$

  for all $i\in {𝒞}_{\text{DS}}$ it holds ${\sum }_{j\in P}{x}_{ij}\ge 1$

• $\mathrm{■}$

  we can bound the cost of the resulting solution by the following:

  • –

    $\text{cost}(x^{\prime },y^{\prime })\le 3\cdot \text{cost}(x,y)+\text{cost}(x^{DS},y^{DS})$ in the $k$-median case

  • –

    ${\text{cost}}^2(x^{\prime },y^{\prime })\le (1+p^2+(1+\frac{1}{p^2})(2+q^2)){\text{cost}}^2(x,y)+(1+\frac{1}{p^2})(1+\frac{1}{q^2}){\text{cost}}^2(x^{DS},y^{DS})$ for $p,q>0$ in the $k$-means case

• $\mathrm{■}$

  all $y_i^{\prime }$ are integral

We first focus on the second requirement. For $i\in {𝒞}_{\text{DS}}$ we look at the set $N(i):=\{p\in P\mid x_{pi}>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\in N(i)$ such that $i$ gets assigned a share of this mass that is equivalent to $x_{pi}$. 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 ${𝒞}_{\text{DS}}$. For this we use the same mapping function $\theta :\{i\in P\mid y_i>0\}\to {𝒞}_{\text{DS}}$ as in Section 2.3.

We denote by $r_p^i:=\frac{x_{pi}}{{\sum }_{l\in P}{x}_{pl}}$ the ratio of $x_{pi}$ to the total mass of assignments on $p$. Note that $r_p^i=0$ if $x_{pi}=0$. Using this notation we define $(x^{\prime },y^{\prime })$ the following way:

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\in {𝒞}_{\text{DS}}$ now does not get all the mass that is assigned to a point $p\in N(i)$ (even if he is the only center sending mass there), but only a fraction of it that is equivalent to $x_{pi}$. This property will later be important when we are bounding the cost of this solution.

The following lemmas show that $(x^{\prime },y^{\prime })$ do indeed have the desired properties. We defer the corresponding proofs to the full version of this paper. Note that the solutions $(x^{\prime },y^{\prime })$ 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.

In this section, we show how to round the fractional assignments $x^{\prime }$ to get an integral solution with small additive violation of the group fairness constraint. We show that the resulting solution $(x^{\prime \prime },y^{\prime })$ has the same cost as $(x^{\prime },y^{\prime })$.

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\}\cup P\cup \{(i,h)\mid i\in {𝒞}_{\text{DS}},h\in H\}\cup {𝒞}_{\text{DS}}$ and the set $E$ of edges is given by $E=A_1\cup A_2\cup A_3\cup A_4$, where $A_1=\{(s,j)\mid j\in P\}$, $A_2=\{(j,(i,h)\mid j\in P,i\in {𝒞}_{\text{DS}},h\in H,x_{ij}^{\prime }>0\}$, $A_3=\{((i,h),i)\mid i\in {𝒞}_{\text{DS}},h\in H\}$ and $A_4=\{(i,t)\mid i\in {𝒞}_{\text{DS}}\}$. All edges have unit capacity. $A_2$ is the only edge set that has nonzero cost. An edge $(p,(i,h))\in A_2$ 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:

• $\mathrm{■}$

  $s$ has balance $|P|$

• $\mathrm{■}$

  All $p\in P$ have balance 0

• $\mathrm{■}$

  All $(i,h)\in {𝒞}_{\text{DS}}\times H$ have balance $-(\lfloor {\sum }_{j\in P_h}{x}_{ij}^{\prime }\rfloor )$

• $\mathrm{■}$

  All $i\in {𝒞}_{\text{DS}}$ have balance $-(\lfloor {\sum }_{j\in P}{x}_{ij}^{\prime }\rfloor -{\sum }_{h\in H}\lfloor {\sum }_{j\in P_h}{x}_{ij}^{\prime }\rfloor )$

• $\mathrm{■}$

  $t$ has balance $-(|P|-{\sum }_{i\in {𝒞}_{\text{DS}}}\lfloor {\sum }_{j\in P}{x}_{ij}^{\prime }\rfloor )$

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^{\prime \prime }$. We show that it satisfies group fairness with an additive violation of 2:

The final solution is then obtained via the pair $(x^{\prime \prime },y^{\prime })$. We defer the proof that this results in Theorem 5 to the full version.