Relax and Merge: A Simple Yet Effective Framework for Solving Fair $k$-Means and $k$-sparse Wasserstein Barycenter Problems

## Abstract

Abstract The fairness of clustering algorithms has gained widespread attention across various areas in machine learning. In this paper, we study fair k 𝑘 k italic_k -means clustering in Euclidean space.
Given a dataset comprising several groups, the fairness constraint requires that each cluster should contain a proportion of points from each group within specified lower and upper bounds.
Due to these fairness constraints, determining the locations of k 𝑘 k italic_k centers and finding the induced partition are quite challenging tasks.
We propose a novel “Relax and Merge” framework that returns a ( 1 + 4 ⁢ ρ + O ⁢ ( ϵ ) ) 1 4 𝜌 𝑂 italic-ϵ (1+4\rho+O(\epsilon)) ( 1 + 4 italic_ρ + italic_O ( italic_ϵ ) ) -approximate solution,  where ρ 𝜌 \rho italic_ρ is the approximate ratio of an off-the-shelf vanilla k 𝑘 k italic_k -means algorithm and O ⁢ ( ϵ ) 𝑂 italic-ϵ O(\epsilon) italic_O ( italic_ϵ ) can be an arbitrarily small positive number. If equipped with a PTAS of k 𝑘 k italic_k -means, our solution can achieve an approximation ratio of ( 5 + O ⁢ ( ϵ ) ) 5 𝑂 italic-ϵ (5+O(\epsilon)) ( 5 + italic_O ( italic_ϵ ) ) with only a slight violation of the fairness constraints, which improves the current state-of-the-art approximation guarantee. Furthermore, using our framework, we can also obtain a ( 1 + 4 ⁢ ρ + O ⁢ ( ϵ ) ) 1 4 𝜌 𝑂 italic-ϵ (1+4\rho+O(\epsilon)) ( 1 + 4 italic_ρ + italic_O ( italic_ϵ ) ) -approximate solution for the k 𝑘 k italic_k -sparse Wasserstein Barycenter problem, which is a fundamental optimization problem in the field of optimal transport, and a ( 2 + 6 ⁢ ρ ) 2 6 𝜌 (2+6\rho) ( 2 + 6 italic_ρ ) -approximate solution for the strictly fair k 𝑘 k italic_k -means clustering with no violation, both of which are better than the current state-of-the-art methods.
In addition, the empirical results
demonstrate that our proposed algorithm
can significantly
outperform baseline approaches in terms of
clustering
cost.

## 1 Introduction

Clustering is one of the most fundamental problems in the area of machine learning. A wide range of practical applications rely on effective clustering algorithms, such as
feature engineering (Glassman et al., ; Alelyani et al., ), image processing (Coleman and Andrews, ; Chang et al., ), and bioinformatics (Ronan et al., ; Nugent and Meila, ).
In particular, the $k$-means clustering problem has been extensively studied in the past decades (Jain, ). Given an input dataset $P\subset\mathbb{R}^{d}$, the goal of the $k$-means problem is to find a set $S$ of at most $k$ points for minimizing the clustering cost, which is the sum of the squared distances from every point of $P$ to its nearest neighbor in $S$.
In recent years, motivated by various fields like education, social security, and cultural communication, the study on *fairness* of clustering has in particular attracted a great amount of attention (Chierichetti et al., ; Bera et al., ; Huang et al., ; Chen et al., ; Ghadiri et al., ).

In this paper, we consider the problem of *$(\alpha,\beta)$-fair $k$-means clustering* that was initially proposed by Chierichetti et al. () and then generalized by Bera et al. ().
Informally speaking, we assume that the given dataset $P$ consists of $m$ groups of points, and the “fairness” constraint requires that in each obtained cluster, the points from each group should take a fraction between pre-specified lower and upper bounds.
Bera et al. () showed that a $\rho$-approximate algorithm for vanilla $k$-means can provide a $(2+\sqrt{\rho})^{2}$- approximate solution (^1^11In their paper, the approximate ratio is written as $(2+\rho)$ because they added a squared root to the $k$-means cost function.) for $(\alpha,\beta)$-fair $k$-clustering with a slight violation on the fairness constraints, where the “violation” is formally defined in Section 2.
Furthermore, Böhm et al. () studied the “strictly” fair $k$-means clustering problem, where it requires that the number of points from each group should be uniform in every cluster; they obtained a $(2+\sqrt{\rho})^{2}$ approximate solution without violation.
These fair $k$-means algorithms can also be accelerated by using the coreset techniques, such as (Huang et al., ; Braverman et al., ; Bandyapadhyay et al., ). There also exist polynomial-time approximation scheme (PTAS) for fair $k$-means, such as the algorithms proposed in (Böhm et al., ; Schmidt et al., ; Bandyapadhyay et al., ), but their methods have an exponential time complexity in $k$.
We are also aware of several other different definitions of fairness for clustering problems, such as the *proportionally fair* clustering (Chen et al., ; Micha and Shah, ) and *socially fair* $k$-means clustering (Ghadiri et al., ).

Another problem closely related to fair $k$-means is the so-called “$k$-sparse Wassertein Barycenter (WB)” (Agueh and Carlier, ) (the formal definition is shown in Section 2).
The Wasserstein Barycenter is a fundamental concept in optimal transport theory, and it represents the “average” or central distribution of a set of probability distributions. It plays a crucial role in various applications such as image processing (Bonneel et al., ; Cuturi and Doucet, ), data analysis (Rabin et al., ), and machine learning (Backhoff-Veraguas et al., ; Metelli et al., ).
Given $m>1$ discrete distributions, the goal of the $k$-sparse WB problem is
to find a discrete distribution (i.e., the barycenter) that minimizes the sum of the Wasserstein distances (Villani, ) between itself to all the given distributions, and meanwhile the support size of the barycenter is restricted to be no larger than a given integer $k\geq 1$.
If relaxing the “$k$-sparse” constraint (*i.e.,* the barycenter is allowed to take a support size larger than $k$), Altschuler and Boix-Adsera () presented an algorithm based on linear programming, which can compute the WB within fixed dimensions in polynomial time.
If the locations of the WB supports are given, the problem is
called “fixed support WB”, which can be solved by using several existing algorithms (Claici et al., ; Cuturi and Doucet, ; Cuturi and Peyré, ; Lin et al., ).
If we keep the “$k$-sparse” constraint, it has been proved that the problem is NP-hard (Borgwardt and Patterson, ). To the best of our knowledge, the current lowest approximation ratio of k-sparse WB problem is also $(2+\sqrt{\rho})^{2}$ (same with the aforementioned approximation factor for fair $k$-means), as recently studied by Yang and Ding ().
In fact, we can regard this problem as a special case of fair $k$-means clustering, where each input distribution is an individual group and the unique cost measured by “Wasserstein distance” is implicitly endowed with a kind of fairness.
This observation from  Yang and Ding () inspires us to consider solving the $k$-sparse WB problem under our framework.

Why fair $k$-means is so challenging?
Though the fair $k$-means clustering has been extensively studied in recent years, their current state-of-the-art approximation qualities are still not that satisfying. The major difficulty arises from the lack of “locality property” (Ding and Xu, ; Bhattacharya et al., ) caused by fair constraints. More precisely, in a clustering result of vanilla $k$-means, each client point obviously belongs to its closest center. That is, a $k$-means clustering implicitly forms a Voronoi diagram, where the cell centers are exactly the $k$ cluster centers, and the client points in each Voronoi cell form a cluster.
However, when we add some fair constraints, such as requiring that the proportion of points of each group should be equal in each cluster, the situation becomes more complicated. Given a set of cluster center locations, because the groups of client points within a Voronoi cell may not be equally distributed, some points are forced to be assigned to other Voronoi cells. This loss of locality introduces significant uncertainty for the selection of cluster center positions.
The previous works (Bera et al., ; Böhm et al., ) do not pay much attention on how to handle this locality issue when searching for the cluster centers, instead, they directly apply vanilla $k$-means algorithms to the entire input dataset or a group, and use the obtained center locations as the center locations for fair $k$-means. It is easy to notice that their methods could result in a certain gap with the optimal fair $k$-means solution. To narrow this gap, we attempt to design some more effective way to determine the center locations, where the key part that we believe, should be how to encode the fair constraints into the searching algorithm.

Our key ideas and main results.
Our key idea relies on an important observation, where we find that the fair $k$-means problem is inherently related to a classic geometric structure, “$\epsilon$-approximate centroid set”, which was firstly proposed by Matoušek (). Roughly speaking, given a dataset, an $\epsilon$-approximate centroid set should contain at least one point that approximately represents the centroid location of any subset of this given dataset. It means that the $\epsilon$-approximate centroid set contains not only the approximate centroids based on the Voronoi diagram, but also the approximate centroids of those potential fairness-preserving clusters.

Inspired by the above observation, we illustrate the relationship between fair $k$-means and $\epsilon$-approximate centroid set first, and then propose a novel *Relax-and-Merge* framework. In this framework, we relax the constraints on the number of clusters $k$; we focus on utilizing fair constraints to cluster the data into small and fair clusters, which are then merged together to determine the positions of $k$ cluster centers.
As shown in Table 1, our result is better than the state of the art works (Bera et al., ; Böhm et al., ).
Equipped with a PTAS for $k$-means problem (e.g., the algorithm from Cohen-Addad et al. ()), our algorithm yields a ${5+O(\epsilon)}$ approximation factor.
We also present two important extensions from our work.
The first extension is an $(1+4\rho+O(\epsilon))$ solution for k-sparse Wasserstein Barycenter.
The second one is about strictly fair $k$-means.
We give a refined algorithm of *Relax and Merge* that yields a no-violation solution with a $(2+6\rho)$ approximation factor, which is better than the state of the art work (Böhm et al., ).

**Table 1: Comparison of the approximation ratios for fair $k$-means and $k$-sparse WB. The “general case” includes $(\alpha,\beta)$-fair $k$-means, strictly $(\alpha,\beta)$-fair $k$-means and $k$-sparse WB.**
| Algorithms | Approximation<br>ratio | When<br>$\rho=1+O(\epsilon)$ | Note on the quality |
| --- | --- | --- | --- |
| Bera et al. () | $(2+\sqrt{\rho})^{2}$ | $9+O(\epsilon)$ | general case |
| Schmidt et al. () | $5.5\rho+1$ | $6.5+O(\epsilon)$ | two groups only |
| Böhm et al. () | $(2+\sqrt{\rho})^{2}$ | $9+O(\epsilon)$ | strictly only, no violation |
| Yang and Ding () | $(2+\sqrt{\rho})^{2}$ | $9+O(\epsilon)$ | $k$-sparse WB |
| Algorithm 1, now | $1+4\rho+O(\epsilon)$ | $5+O(\epsilon)$ | general case |
| Algorithm 2, now | $2+6\rho$ | $8+O(\epsilon)$ | strictly only, no violation |

Other Related Works on $k$-Means
The vanilla $k$-means problem is a topic that has been widely studied in both theory and practice. It has been proved that $k$-means clustering is NP-hard even in $2D$ if $k$ is large (Mahajan et al., ). In high dimensions, even if $k$ is fixed, say $k=2$, the $k$-means problem is still NP-hard (Drineas et al., ). Furthermore, Lee et al. () proved the APX-hardness result for Euclidean $k$-means problem, which implies that it is impossible to approximate the optimal solution of $k$-means below a factor 1.0013 in polynomial time under the assumption of P $\neq$ NP. Therefore, a number of approximation algorithms have been proposed in theory.
If the dimension $d$ is fixed, Kanungo et al. () obtained a ($9+O(\epsilon)$)-approximate solution
by using the local search technique. Roughly speaking, the idea of local search is swapping a small number of points in every iteration, so as to incrementally improve the solution until converging at some local optimum. Following this idea, Cohen-Addad et al. () and Friggstad et al. () proposed the PTAS for $k$-means in low dimensional space. For high-dimensional case with constant $k$, Kumar et al. () proposed an elegant peeling algorithm that iteratively finds the $k$ cluster centers and eventually obtain the PTAS.

## 2 Preliminaries

Notations. In this paper, we always assume that the dimensionality $d$ of the Euclidean space is constant. Let $P$ denote the set of $n$ client points located in Euclidean space $\mathbb{R}^{d}$.
The set $P$ consists of $m$ different groups (not necessarily disjoint), *i.e.*, $\bm{P=\cup_{i=1}^{m}P^{(i)}}$, and each group has the size $\bm{|P^{(i)}|=n^{(i)}}$ (we use the superscript “$(i)$”
to denote the group’s index). The Euclidean distance between two points $a,b\in\mathbb{R}^{d}$ is denoted by $\|a-b\|$; the distance between a point $a$ and any set $Q\subset\mathbb{R}^{d}$ is denoted by $\mathtt{dist}(a,Q)=\min_{q\in Q}\|a-q\|$, and the nearest neighbor of $a$ in $Q$ is denoted as $\mathcal{N}(a,Q)$.
The centroid of a set $Q$ is denoted by $\mathtt{Cen}(Q)$.

For the vanilla $k$-means problem, the client points are always assigned to their nearest center. However, if considering the fairness constraint, the assignment may not be that straightforward. To describe the fair $k$-means clustering more clearly, we introduce the “assignment matrix” first. Given any candidate set of $k$ cluster centers $S$, we define the assignment matrix
$\bm{\phi_{S}}:P\times S\rightarrow\mathbb{R}^{+}$ to indicate the assignment relation between the client points and cluster centers.
For every $p\in P$ and $s\in S$, $\phi_{S}(p,s)$ denotes the proportion that
is assigned to center $s$ (e.g., we may respectively assign $30\%$ and $70\%$ to two different centers). Obviously, we have $\sum_{s\in S}\phi_{S}(p,s)=1$.
For each center $s\in S$, we use $w(s)=\sum_{p\in P}\phi_{S}(p,s)$ to denote the amount of weight assigned to $s$; for each group $P^{(i)}$, we similarly define the function $w^{(i)}(s)=\sum_{p\in P^{(i)}}\phi_{S}(p,s)$. Let $\mathtt{Cost}(P,S,\phi_{S})$ denote the cost of input instance $P$ with given $S$ and $\phi_{S}$:

$$ $\displaystyle\mathtt{Cost}(P,S,\phi_{S})=\sum_{p\in P}\sum_{s\in S}\|p-s\|^{2} \phi_{S}(p,s).$ (1) $$

###### Problem 1 ( $(\alpha,\beta)$ -fair $k$ -means clustering (Bera et al., 2019 ) ) .

Given an instance $P$ as described above
and two parameter vectors $\alpha,\beta\in[0,1]^{m}$, the goal of the $\bm{(\alpha,\beta)}$-fair $\bm{k}$-means clustering is to find the set $S$ consisting of $k$ points and an assignment matrix $\phi_{S}$, such that the clustering cost (1) is minimized,
and meanwhile each cluster center $s\in S$ should satisfy the fairness constraint: $\beta_{i}w(s)\leq w^{(i)}(s)\leq\alpha_{i}w(s)$ for every
$i\in\{1,2,\cdots,m\}$. Here, we use $\alpha_{i},\beta_{i}$ to denote the $i$-th entry of $\alpha$ and $\beta$, respectively.

Moreover, if the $m$ groups are disjoint with equal size (i.e., $n^{(i)}=n/m$ for any $i$), and $\alpha_{i}=\beta_{i}=1/m$ for each group $P^{(i)}$, we say this is a strictly $\bm{(\alpha,\beta)}$-fair $\bm{k}$-means clustering problem.

For Problem 1, we can specify two types of solutions: fractional and integral. Their difference is only from the restriction on the assignment matrix $\phi_{S}$. For the first one, each entry $\phi_{S}(p,s)$ can be any real number between 0 0 and $1$; but for the latter one, we require that the value of $\phi_{S}(p,s)$ should be either 0 0 or $1$, that is, the whole weight of $p$ should be assigned to only one cluster center.

How to round a fractional solution into integral while preserving fairness constraints is still an open problem. Bera et al. () introduced the violation factor to measure the violations of fairness constraints after rounding: an assignment matrix $\phi_{S}$ is a $\lambda$-violation solution if $\beta_{i}\sum_{p\in P}\phi_{S}(p,s)-\lambda\leq\sum_{p\in P^{(i)}}\phi_{S}(p,s
)\leq\alpha_{i}\sum_{p\in P}\phi_{S}(p,s)+\lambda,\quad\forall s\in S,\forall i
\in[m]$.
In their paper, a fractional solution can always be rounded to integral, but it introduces some violations , which will be discussed in Section 3.1.
In this paper, we use $OPT$ to denote the optimal integral cost of Problem 1. We use $S_{\mathtt{opt}}=\{\tilde{s}_{1},\tilde{s}_{2},\cdots,\tilde{s}_{k}\}$ to denote the optimal solution of integral fair $k$-means problem and its assignment matrix is denoted by $\phi_{S_{\mathtt{opt}}}$.
For each $\tilde{s}_{j}$, let $C_{j}=\{p\in P\mid\phi_{S_{\mathtt{opt}}}(p,\tilde{s}_{j})>0\}$ be the corresponding cluster, i.e., the set of point assigned to it.
A simple observation is that, if given a fixed candidate cluster centers set $S$, the assignment matrix
$\phi_{S}$ can be obtained via solving a linear programming (we can view the $n\times k$ entries of $\phi_{S}$ as the variables):

$$ $\displaystyle\min_{\phi_{S}}$ $\displaystyle\sum_{p\in P}\sum_{s\in S}\|p-s\|^{2}\phi_{S}(p,s)$ (2) $\displaystyle s.t.$ $\displaystyle\beta_{i}\sum_{p\in P}\phi_{S}(p,s)\leq\sum_{p\in P^{(i)}}\phi_{S }(p,s)\leq\alpha_{i}\sum_{p\in P}\phi_{S}(p,s),\quad\forall s\in S,\forall i \in[m],$ $\displaystyle\sum_{s\in S}\phi_{S}(p,s)=1,\quad\forall p\in P.$ $$

If we want to compute an integral solution, the above (2) should be an integer LP.
Given a set $S$, $\bm{\phi_{S}^{*}}$ denotes the optimal solution of (2) and $\bm{\tilde{\phi}_{S}}$ denotes the corresponding optimal integral solution.

The following proposition is a folklore result that has been used in many articles on clustering algorithms (e.g., (Kanungo et al., )). We will also repeatedly use it in our proofs.

###### Proposition 1 .

Given a finite weighted point set $Q\subset\mathbb{R}^{d}$,
for any point $a$,
$\sum_{q\in Q}w(q)\|a-q\|^{2}=\sum_{q\in Q}w(q)\|q-\mathtt{Cen}(Q)\|^{2}+w(Q)
\cdot\|a-\mathtt{Cen}(Q)\|^{2}$, where $w(Q)$ is the total weight of $Q$.

Next we introduce an important geometric structure “$\epsilon$-approximate centroid set”, which was
firstly proposed by Matoušek ().
Roughly speaking, the $\epsilon$-approximate centroid set approximately covers the centroids of any subset of given data, even though the subsets do not align with the “Voronoi diagram” structure (as discussed in Section 1).

###### Definition 1 .

Given a finite set $P\subset\mathbb{R}^{d}$ and a small parameter $\epsilon>0$, we use $\mathtt{CS}_{\epsilon}(P)$ to denote an $\epsilon$-approximate centroid set of $P$ that satisfies: for any nonempty subset $Q\subseteq P$, there always exists a point $v\in\mathtt{CS}_{\epsilon}(P)$ such that $\|v-\mathtt{Cen}(Q)\|\leq\frac{\epsilon}{3}\sqrt{\frac{1}{|Q|}\sum_{q\in Q}\|q
-\mathtt{Cen}(Q)\|^{2}}$.

###### Remark 1 .

Matoušek () also presented a construction algorithm based on the space partitioning technique “quadtree” (Finkel and Bentley, ). In Appendix A, we briefly illustrate the role of the $\epsilon$-approximate centroid set in preserving fairness constraints and how to construct it.
The size of the obtained $\epsilon$-approximate centroid set is $O(|P|\epsilon^{-d}\log(1/\epsilon))$ and the construction time complexity is $O(|P|\log|P|+|P|\epsilon^{-d}\log(1/\epsilon))$.

Next, we give the formal definition of $k$-sparse Wasserstein Barycenter problem.

###### Definition 2 (Wasserstein Distance) .

Let $P$ and $Q$ be weighted point sets supported in $\mathbb{R}^{d}$. Wasserstein distance is the minimum transportation cost between $P$ and $Q$:
$\mathcal{W}(P,Q)=\min_{F}\sqrt{\sum_{p\in P}\sum_{q\in Q}F(p,q)\|p-q\|^{2}}$,
where the transport matrix $F:P\times Q\rightarrow[0,1]$ should satisfy: $\sum_{p\in P}F(p,q)=w(q)$ for any $q\in Q$, and $\sum_{q\in Q}F(p,q)=w(p)$ for any $p\in P$.

For a weighted set $S$, we use $\mathtt{supp}(S)$ to denote its support, i.e., the set that shares the same location of $S$ but not weighted.
The number of points is $\mathtt{supp}(S)$ is denoted by $|\mathtt{supp}(S)|$.

###### Problem 2 ( $k$ -sparse Wassertein Barycenter ( $k$ -sparse WB)) .

Given $m$ discrete probability distributions $P^{(1)},\cdots,P^{(m)}$ supported on $\mathbb{R}^{d}$, *WB* is the probability distribution $S$ minimizing the sum of squared Wasserstein distances to them, i.e.,
$\arg\min_{S}\sum_{i=1}^{m}\mathcal{W}^{2}(P^{(i)},S)$.
The problem is called $k$-sparse Wasserstein Barycenter if we restrict $|\mathtt{supp}(S)|\leq k$

In Section 3.2, we explain why this problem can be regarded as a fair $k$-means clustering.

###### Problem 1 ( ( α , β ) 𝛼 𝛽 (\alpha,\beta) ( italic_α , italic_β ) -fair k 𝑘 k italic_k -means clustering (Bera et al., 2019 ) ) .

###### Proposition 1 .

###### Definition 1 .

###### Remark 1 .

###### Definition 2 (Wasserstein Distance) .

###### Problem 2 ( k 𝑘 k italic_k -sparse Wassertein Barycenter ( k 𝑘 k italic_k -sparse WB)) .

## 3 Our “Relax and Merge” Framework

In general, there are two stages in clustering with fair constraints. The first stage is to find the proper locations of clustering centers, and the second stage is to assign all the client points to the centers by solving LP (2). The previous approaches often use the vanilla $k$-means in the first stage to obtain the location of centers, and then take the fairness into account in the second stage (Bera et al., ; Böhm et al., ). In our proposed framework, we aim to shift the consideration of fair constraints to the first stage, so as to achieve a lower approximation factor in the final result. The following theorem is our main result.

###### Theorem 1 .

Given an instance of Problem 1 and a $\rho$-approximate vanilla $k$-means clustering algorithm, there exists
an algorithm that can return a fractional $(1+4\rho+O(\epsilon))$ approximate solution for Problem 1. Further,
one can apply a rounding method to transform this fractional solution to an integral one with a constant violation factor while ensuring the cost does not increase.

The details for computing the fractional solution are shown in Algorithm 1. The set $T$ in Algorithm 1
contains the approximate centroids of all the potential clusters with preserving fair constraints.
Then we solve a linear program to obtain the relaxed solution $(T,\phi^{*}_{T})$ that also preserves the fair constraints. Because of that, the following $k$-means procedure is able to determine the appropriate locations for the cluster centers of Problem 1.

Figure: Algorithm 1 Fractional Fair $k$-means

###### Theorem 1 .

### 3.1 Algorithm for ( α , β ) 𝛼 𝛽 (\alpha,\beta) ( italic_α , italic_β ) Fair k 𝑘 k italic_k -means Problem

In this section, we mainly focus on the fractional version of $(\alpha,\beta)$-fair $k$-means problem. More precisely, we allow the value of the assignment function $\phi_{S}$ to be a real number in $[0,1]$ rather than $\{0,1\}$. To prove Theorem 1, we need the following lemmas first.
Specifically, Lemma 1 provides the bound for the cost from the merged solution $S$; Lemma 2 shows that the $\epsilon$-approximate centroid set provides a satisfied relaxed solution with a cost no more than $(1+O(\epsilon))OPT$. Combining with the rounding methods, Theorem 1 can be obtained.

###### Lemma 1 .

Let $\eta$ be any positive number. If we suppose $\mathtt{Cost}(P,T,\phi_{T}^{*})\leq\eta\cdot OPT$, then the solution $(S,\phi_{S}^{*})$ returned by Algorithm 1 is an $\big{(}\eta+(2\eta+2)\rho\big{)}$-approximate solution for Problem 1.

###### Proof.

According to the definition of fractional fair $k$-means problem, the cost can be written as

$$ $\displaystyle\mathtt{Cost}(P,S,\phi_{S}^{*})$ $\displaystyle=\sum_{p\in P}\sum_{s\in S}\|p-s\|^{2}\phi_{S}^{*}(p,s).$ (3) $$

Now we consider another assignment strategy: we firstly assign $P$ to $T$ according to $\phi_{T}^{*}$ ( recall that $\phi_{T}^{*}$ is the optimal fractional assignment matrix from $P$ to $T$), and then we assign every weighted point in $T$ to some $s\in S$ such that $s$ is closest point to $\pi(t)$. Since $\phi_{S}^{*}$ is the optimal assignment matrix from $P$ to $S$, the cost of this assignment strategy should have:

$$ $\displaystyle\sum_{p\in P}\sum_{t\in T}\|p-\mathcal{N}(\pi(t),S)\|^{2}\phi_{T} ^{*}(p,t)$ $\displaystyle\geq\mathtt{Cost}(P,S,\phi_{S}^{*}).$ (4) $$

Since $\pi(t)$ is the centroid of the weighted points assigned to $t$, according to Proposition 1, we know the left-hand side of (4) should have the upper bound

$$ $\displaystyle\sum_{t\in T}\Big{[}\sum_{p\in P}\|p-\pi(t)\|^{2}\phi_{T}^{*}(p,t )+\|\pi(t)-\mathcal{N}(\pi(t),S)\|^{2}w(t)\Big{]}$ (5) $\displaystyle=\underbrace{\sum_{p\in P}\sum_{t\in T}\|p-\pi(t)\|^{2}\phi_{T}^{ *}(p,t)}_{\text{(a)}}+\underbrace{\sum_{t\in T}\|\pi(t)-\mathcal{N}(\pi(t),S) \|^{2}w(t)}_{(b)}.$ $$

Then we bound (a) and (b) separately.

$$ $\displaystyle(a)=\sum_{p\in P}\sum_{t\in T}\|p-\pi(t)\|^{2}\phi_{T}^{*}(p,t) \leq\sum_{p\in P}\sum_{t\in T}\|p-t\|^{2}\phi_{T}^{*}(p,t)\leq\eta\cdot OPT.$ (6) $$

The first inequality holds because $\pi(t)$ is the centroid of the weighted points assigned to $t$, minimizing the weighted sum of the squared distances between them.
The second inequality holds because $\mathtt{Cost}(P,T,\phi_{T}^{*})\leq\eta\cdot OPT$.
Next, we focus on (b).
Suppose $S_{means}$ is the optimal $k$-means solution of $T$. Then we have:

$$ $\displaystyle(b)$ $\displaystyle=\sum_{t\in T}\|\pi(t)-\mathcal{N}(\pi(t),S)\|^{2}w(t)\leq\rho \sum_{t\in T}\|\pi(t)-\mathcal{N}(\pi(t),S_{means})\|^{2}w(t)$ (7) $\displaystyle=\rho\sum_{p\in P}\sum_{t\in T}\|\pi(t)-\mathcal{N}(\pi(t),S_{ means})\|^{2}\phi_{T}^{*}(p,t)$ $\displaystyle=\rho\sum_{p\in P}\sum_{t\in T}\big{[}\sum_{\tilde{s}\in S_{opt}} \|\pi(t)-\mathcal{N}(\pi(t),S_{means})\|^{2}\phi_{S_{opt}}^{*}(p,\tilde{s}) \big{]}\phi_{T}^{*}(p,t)$ $\displaystyle\leq\rho\sum_{p\in P}\sum_{t\in T}\big{[}\sum_{\tilde{s}\in S_{ opt}}\|\pi(t)-\tilde{s}\|^{2}\phi_{S_{opt}}^{*}(p,\tilde{s})\big{]}\phi_{T}^{* }(p,t).$ $$

Further, according to squared triangle inequality, we have

$$ $\displaystyle(b)$ $\displaystyle\leq\rho\sum_{p\in P}\sum_{t\in T}\Big{[}\sum_{\tilde{s}\in S_{ opt}}\big{[}\|\pi(t)-p\|+\|p-\tilde{s}\|\big{]}^{2}\phi_{S_{opt}}^{*}(p,\tilde {s})\Big{]}\phi_{T}^{*}(p,t)$ (8) $\displaystyle\leq\rho\sum_{p\in P}\sum_{t\in T}\sum_{\tilde{s}\in S_{opt}}2\| \pi(t)-p\|^{2}\phi_{S_{opt}}^{*}(p,\tilde{s})\phi_{T}^{*}(p,t)$ $\displaystyle+\rho\sum_{p\in P}\sum_{t\in T}\sum_{\tilde{s}\in S_{opt}}2\|p- \tilde{s}\|^{2}\phi_{S_{opt}}^{*}(p,\tilde{s})\phi_{T}^{*}(p,t)$ $\displaystyle=2\rho\sum_{p\in P}\sum_{t\in T}\|\pi(t)-p\|^{2}\phi_{T}^{*}(p,t) +2\rho\sum_{p\in P}\sum_{\tilde{s}\in S_{opt}}\|p-\tilde{s}\|^{2}\phi_{S_{opt} }^{*}(p,\tilde{s}).$ $$

The last equality holds because for any $p\in P$, $\sum_{\tilde{s}\in S_{opt}}\phi_{S_{opt}}^{*}(p,\tilde{s})=1$.
The first term is exactly $2\rho$ times of (a) and the second term equals $2\rho\cdot OPT$.
Through combining (a) and (b), we can obtain an approximation factor of $\eta+(2\eta+2)\rho$.
∎

Algorithm 1 reduces the fair $k$-means problem to computing the set $T$. The following lemma shows that an $\epsilon$-approximate centroid set is a good candidate for $T$.

###### Lemma 2 .

If $T$ is an $\epsilon$-approximate centroid set of $P$, then $\mathtt{Cost}(P,T,\phi_{T}^{*})\leq(1+O(\epsilon))OPT$.

###### Proof.

According to Definition 1, let $t_{i}\in T$ denote the point such that $\|t_{i}-\mathtt{Cen}(C_{i})\|\leq\frac{\epsilon}{3}\sqrt{\frac{1}{|C_{i}|}\sum
_{p\in C_{i}}\|p-\mathtt{Cen}(C_{i})\|^{2}}$. Let $T^{\prime}=\{t_{1},\cdots,t_{k}\}$.
A key observation is that each optimal center $\tilde{s}_{i}$ is always the centroid of $C_{i}$, *i.e.*, $\mathtt{cen}(C_{i})=\tilde{s}_{i}$, so we have $\|t_{i}-\mathtt{Cen}(C_{i})\|^{2}\leq\frac{\epsilon^{2}}{9|C_{i}|}\sum_{p\in C
_{i}}\|p-\tilde{s}_{i}\|^{2}=\frac{\epsilon^{2}}{9|C_{i}|}OPT_{i}$, where $OPT_{i}=\sum_{p\in C_{i}}\|p-\tilde{s}_{i}\|^{2}$.

If we assign all points of $C_{i}$ to $t_{i}$, the cost of every $C_{i}$ can be written as $\sum_{p\in C_{i}}\|t_{i}-p\|^{2}=$

$$ $\displaystyle\begin{aligned} &\sum_{p\in C_{i}}\|t_{i}-\tilde{s}_{i}\|^{2}+ \sum_{p\in C_{i}}\|p-\tilde{s}_{i}\|^{2}\leq\frac{\epsilon^{2}}{9}OPT_{i}+OPT_ {i}=(1+O(\epsilon))OPT_{i}.\end{aligned}$ (9) $$

The first equality holds due to Proposition 1. Since $\phi^{*}_{T^{\prime}}$ is the optimal assignment matrix of $T^{\prime}$, $\mathtt{Cost}(P,T^{\prime},\phi^{*}_{T^{\prime}})\leq\sum_{i=1}^{k}\sum_{p\in C
_{i}}\|t_{i}-p\|^{2}\leq(1+O(\epsilon))\sum_{i=1}^{k}OPT_{i}\leq(1+O(\epsilon)
)OPT$.
Finally, since $T^{\prime}$ is a subset of $T$, we have $\mathtt{Cost}(P,T,\phi^{*}_{T})\leq\mathtt{Cost}(P,T^{\prime},\phi^{*}_{T^{
\prime}})\leq(1+O(\epsilon))OPT$.
∎

Through combining Lemma 1 and Lemma 2, we can immediately obtain Lemma 3.

###### Lemma 3 .

Equipped with the $\epsilon$-approximate centroid set by Matoušek (), the cost of the solution returned by Algorithm 1 is at most $(1+4\rho+O(\epsilon))OPT$. Furthermore, by utilizing the PTAS of vanilla $k$-means algorithm, the cost of the solution is at most $(5+O(\epsilon))OPT$.

Rounding for integral solution. Note that Lemma 3 only guarantees a fractional solution. Recall the “violation factor” introduced in Section 2. According to the rounding method proposed in (Bera et al., ), a fractional solution of Problem 1 can be rounded to be integral with $(3\Delta+4)$ violation, where $\Delta$ is the maximum number of groups a point can join in (e.g., if a point can belong to three groups, $\Delta$ should be equal to $3$). Their main idea is to reduce the fair assignment problem to the *minimum degree-bounded matroid basis* (MBDMB) problem, and then solve the MBDMB by iteratively solving a linear program (LP). In the current article, we further propose a new rounding method that can improve this violation factor to “$2$” when assuming $\Delta=1$, *i.e.*, the groups are mutually disjoint, and the each point belongs to exactly one group (if using the method of (Bera et al., ), the factor should be $7$).
Actually, it is natural to assume that the groups are disjoint, e.g., each person may belong to one race.
Fair clustering problem in disjoint groups has also been studied in
Bercea et al. (); Wu et al. (); Chierichetti et al. ().
Our key idea is building a “hub-guided” minimum cost circulation problem. Roughly speaking, we utilize a set of carefully designed “hubs” in a transportation network, for guiding the integral fair matching between the input points and the obtained cluster centers. We show the result in Lemma 4, and place the proof to Appendix C due to the space limit.

###### Lemma 4 .

If the groups are mutually disjoint, one can round the fractional solution returned by Algorithm 1 to be integral with at most $2$-violation, while the cost does not increase.

Finally, Theorem 1 can be obtained by combining either the rounding method from (Bera et al., ) for general case, or Lemma 4 for disjoint case.

Overall time complexity. As we mentioned in Remark 1, computing an $\epsilon$-approximate centroid set of $P$ needs $O(n\log n+n\epsilon^{-d}\log(1/\epsilon))$ time.
The adjustment of the location of $T$ can be completed in $O(kn)$ time.
Suppose the time complexities of linear programming, vanilla $k$-means are denoted by $\mathcal{T}_{LP}$ and $\mathcal{T}_{means}$, respectively. The overall time complexity of Algorithm 1 is $O(n\log n+n\epsilon^{-d}\log(1/\epsilon))+\mathcal{T}_{LP}+O(kn)+\mathcal{T}_{means}$. It is worth noting the the complexity can be further reduced by using the assignment preserving coreset ideas (Huang et al., ; Braverman et al., ; Bandyapadhyay et al., ). By doing this, we need to introduce an extra running time for coreset construction, which is linear to $n$, but we can compress the data size from $n$ to $poly(k,\epsilon)$.

###### Lemma 1 .

###### Proof.

###### Lemma 2 .

###### Proof.

###### Lemma 3 .

###### Lemma 4 .

### 3.2 Extension to k 𝑘 k italic_k -sparse Wasserstein Barycenter

A cute property of Algorithm 1 is that it can be easily extended to address the $k$-sparse WB problem.
Recall the definition of $k$-sparse WB in Problem 2.
The given $m$ distributions can be viewed as $m$ groups of weighted points. And the sum of Wasserstein distances between barycenter and given distributions can be rewritten as the sum of squared Euclidean distances from $P$ to the centers. Moreover, the flows induced by Wasserstein distances between barycenter and the given distributions can implicitly ensure the fairness, *i.e.*, for each point $s$ in barycenter, $w^{(i)}(s)=\frac{1}{m}w(s)$ for any $i\in[m]$. Namely,
we can directly perform our “Relax and Merge” framework by setting $\alpha_{i}=\beta_{i}=1/m$.
First, we calculate the $\epsilon$-approximate centroid (here we ignore the weight of points) set to obtain $T$, then we use $T$ as the support of the Barycenter to run a “fixed support”
WB algorithm (Claici et al., ; Cuturi and Doucet, ; Cuturi and Peyré, ; Lin et al., ) to obtain the weights of $T$ (due to the space limit, we leave some details on fixed support WB algorithms to Appendix D).
Finally, we run a vanilla $k$-means algorithm on $T$ to obtain the $k$-sparse solution.

###### Theorem 2 .

If $T$ is
an $\epsilon$-approximate centroid set
of $\cup_{i=1}^{m}P^{(i)}$, Algorithm 1 returns a $(1+4\rho+O(\epsilon))$-approximate solution for $k$-sparse Wasserstein Barycenter problem.

###### Theorem 2 .

### 3.3 Strictly Fair k 𝑘 k italic_k -means without Violation

Since the strictly fair $k$-means is a special case of $(\alpha,\beta)$-fair $k$-means, by using Algorithm 1 and the rounding technique introduced by Section 3.1, we can obtain an integral solution but with certain violation. In this section, we consider how to obtain an integral solution with no violation. Specifically, we compute the fairlet decomposition (Chierichetti et al., ) for the input groups and use its centroids as the relaxed solution $T$ rather than $\epsilon$-approxiamte centroid set. First, we give the definition of fairlet decomposition for multiple groups, which extends the original definition of (Chierichetti et al., ) from two groups to multiple groups.

###### Definition 3 (Fairlet Decomposition) .

Given a dataset $P$ that has $m$ equal-sized disjoint groups, We say a set $G$ of $m$ points is a fairlet of $P$, if $G$ contains exactly one point from each group of $P$. A set $\mathcal{G}$ of $n/m$ fairlets is a fairlet decomposition of $P$, if all fairlets in $\mathcal{G}$ are disjoint, where $n/m$ is the number of points in each group of $P$.

We define the cost of fairlet decomposition $\mathcal{G}$ as $\mathtt{Cost_{fairlet}}(\mathcal{G})=\sum_{G\in\mathcal{G}}\sum_{p\in G}\|p-
\mathtt{Cen}(G)\|^{2}$. It is easy to know that fairlet decomposition is indeed a solution of strictly fair $n/m$-means. Hence, we can still use the “Relax and Merge” technique: regard the centroids of fairlets in fairlet decomposition as a relaxed solution, and then run $\rho$-approximate vanilla $k$-means algorithm on these centroids. So, we reduce the strictly fair $k$-means problem to the fairlet decomposition problem. We propose Algorithm 2, which first computes a $2$-approximate fairlet decomposition and then generates a $(2+6\rho)$-approximate integral solution for strictly fair $k$-means.

Figure: Algorithm 2 Stricytly Fair $k$-means

###### Theorem 3 .

Algorithm 2 returns a $(2+6\rho)$-approximate integral solution of strictly fair $k$-means.

To prove Theorem 3, we need to prove the following lemma, which shows that $\mathcal{G}$ is a 2-approximate fairlet decomposition. Then, we can use the same idea of Lemma 1 to obtain Theorem 3. Recall that Lemma 1 shows that if we have a relaxed solution $T$ with a bounded cost $\eta\cdot OPT$, then the merged solution will have constant approximate ratio. Here, $T$ obtained by Algorithm 2 also provides a relaxed solution whose cost does not exceed $2OPT$. Hence, after we merge $T$ and obtain $S$, the approximate ratio should no more than $(\eta+(2\eta+2)\rho)=2+6\rho$. Furthermore, if we use PTAS for $k$-means, the overall approximate ratio of Algorithm 2 is $8+O(\epsilon)$.

###### Lemma 5 .

If $\mathcal{G}$ is the fairlet decomposition obtained by Algorithm 2, then $\mathtt{Cost}_{fairlet}(\mathcal{G})\leq 2OPT$.

###### Proof.

Suppose $G$ is a fairlet, and we use $G^{(i)}$ to denote the point in $G$ and belongs to group $P^{(i)}$, *i.e.*, $G^{(i)}=G\cap P^{(i)}$. We use $\mathcal{G}_{OPT}$ to denote the optimal fairlet decomposition that has the lowest cost (we cannot obtain $\mathcal{G}_{OPT}$ in reality, and here we just use it for conducting our analysis). For each $p\in P$, let $\mathcal{G}_{OPT}(p)$ denote the fairlet of $\mathcal{G}_{OPT}$ that $p$ belongs to, *i.e.*, $p\in\mathcal{G}_{OPT}$. Suppose that $P^{(u)}$ is the “closest” group to $\mathcal{G}_{OPT}$, *i.e.*
$u=\arg\min_{i\in[m]}\sum_{p\in P^{(i)}}\|\mathtt{Cen}(\mathcal{G}_{OPT}(p))-p
\|^{2}$.
We have

$$ $\displaystyle\begin{aligned} &\mathtt{Cost}_{fairlet}(\mathcal{G})=\sum_{G\in \mathcal{G}}\sum_{p\in G}\|p-\mathtt{Cen}(G)\|^{2}\\ &\leq\sum_{G\in\mathcal{G}}\sum_{p\in G}\|p-\mathtt{Cen}(G)\|^{2}+m\sum_{G\in \mathcal{G}}\|G^{(v)}-\mathtt{Cen}(G)\|^{2}\end{aligned}$ (10) $$

According to Proposition 1, the right side of (10) equals to $\sum_{p\in P^{(v)}}\sum_{j=1}^{m}\|p-\tau_{vj}(p)\|^{2}$, so we have
$\mathtt{Cost}_{fairlet}(\mathcal{G})\leq$

$$ $\sum_{p\in P^{(v)}}\sum_{j=1}^{m}\|p-\tau_{vj}(p)\|^{2}\leq\sum_{p\in P^{(u)}} \sum_{j=1}^{m}\|p-\tau_{uj}(p)\|^{2}\leq\sum_{p\in P^{(u)}}\sum_{j=1}^{m}\|p-( \mathcal{G}_{OPT}(p))^{(j)}\|^{2}.$ (11) $$

The first inequality holds because $v=\arg\min_{i}\sum_{p\in P^{(i)}}\sum_{j=1}^{m}\|p-\tau_{ij}(p)\|^{2}$. And the last inequality holds because $\tau$ is the perfect one-to-one matching. Using Proposition 1 again, we have $\mathtt{Cost}_{OPT}(\mathcal{G})\leq$

$$ $\displaystyle\sum_{p\in P^{(u)}}\sum_{j=1}^{m}\|\mathtt{Cen}(\mathcal{G}_{OPT} (p))-(\mathcal{G}_{OPT}(p))^{(j)}\|^{2}+m\sum_{p\in P^{(u)}}\|\mathtt{Cen}( \mathcal{G}_{OPT}(p))-p\|^{2}.$ (12) $$

Note that $\mathcal{G}$ is the optimal fairlet decomposition, as well as the optimal strictly fair $n/m$-means solution, so the first term of (12) should be at most $OPT$. As for the second term, since $P^{(u)}$ is the “closest” group to $\mathcal{G}$, it should be no larger than $m\cdot\frac{1}{m}OPT\leq OPT$ (because the minimum distance “$\sum_{p\in P^{(u)}}\|\mathtt{Cen}(\mathcal{G}_{OPT}(p))-p\|^{2}$” should not exceed the average distance $\frac{1}{m}OPT$). Overall, we complete the proof of Lemma 5.
∎

###### Definition 3 (Fairlet Decomposition) .

###### Theorem 3 .

###### Lemma 5 .

###### Proof.

## 4 Experiments

In this section, we perform the empirical evaluation on our algorithms.
Our experiments are conducted on a server equipped with Intel(R) Xeon(R) Gold 6154 CPU @ 3.00GHz CPU and 512GB memory. We implement our algorithms in C++ and python (with linear programming solver gurobi (Gurobi Optimization, LLC, )).
We use the following datasets which are commonly used in previous works: Bank (Moro et al., )(4522 points with 5 groups), Adult (Becker and Kohavi, ) (32561 points with 7 groups),
Census (Zhou and Chen, )(50000 points with 10 groups), creditcard (Yeh and Lien, ) (30000 points with 8 groups),
Biodeg (Mansouri et al., ) (1055 points with 2 groups),
Breastcancer (Wolberg,William, Mangasarian,Olvi, Street,Nick, and
Street,W., ) (570 points with 2 groups), Moons (scikit-learn developers, ) (200 points with 2 groups),
Hypercube(200 points with 2 groups),
Cluto (Karypis et al., ) (800 points with 8 groups), and Complex (800 points with 8 groups). The last four datasets consist of disjoint and equal sized groups, so we can perform strictly fair $k$-means algorithms on them. We place the detailed information of these datasets in Appendix E. Regarding the selection of $\alpha$ and $\beta$, we set $\alpha_{i}=\beta_{i}=\frac{|P^{(i)}|}{|P|}$ and we also discuss more choices for $\alpha$ and $\beta$, and provide more experimental results, including the part of $k$-sparse Wasserstein Barycenter, in the Section E of the appendix.

Results on $(\alpha,\beta)$-Fair $k$-means. We compared the cost of $(\alpha,\beta)$-fair $k$-means of our Algorithm 1 and baselines. We choose the algorithm proposed by Bera et al. () (denoted by NIPS19) and Böhm et al. () (denoted by ORL21) as the baselines. The construction of an $\epsilon$-approximate centroid set is a theoretical algorithm that can be replaced by some efficient methods in practice. In our experiments, we adopted the alternative implementation of Kanungo et al. (), which combines the kd-tree (Friedman et al., ) and a sampling technique.
Figure 1 shows that our algorithm gives the lowest cost of $(\alpha,\beta)$-fair $k$-means, indicating that Algorithm 1 can find better center locations. This improvement is possible due to that
our method considers the fairness information of groups when choosing the locations of centers.

Figure: Figure 1: The cost obtained by the algorithms with different $k$.
Refer to caption: extracted/5972673/cost4.png

Results on Strictly Fair $k$-means.
We compare our strictly fair $k$-means algorithm with the state-of-the-art algorithm ORL21 (Böhm et al., ). Both ORL21 and Algorithm 2 can return integral solution with no violation. Figure 2 shows that our method has significant advantage in terms of the clustering cost.

Figure: Figure 2: The cost of strictly fair $k$-means.
Refer to caption: extracted/5972673/integral3.png

## 5 Conclusion

In this paper, we utilize the insight on the relationship between the fair $k$-means problem and a classic geometric structure, $\epsilon$-approximate centroid set, for developing a novel “Relax and Merge” framework. It can achieve a $(1+4\rho+O(\epsilon))$ approximation ratio of fair $k$-means and $k$-sparse Wasserstein Barycenter problems, which improves the current state-of-the-art approximation guarantees.
There still exists some open problems: how to obtain an integral approximate solution of general case without violation? In addition, is it possible to extend our ‘Relax and Merge” framework to other types of clustering problems, such as the proportionally fair clustering (Chen et al., ) and socially fair $k$-means clustering (Ghadiri et al., ).

## 6 Acknowledgement

The authors want to thank Prof. Lingxiao Huang for the meaningful discussion about the rounding algorithm in Appendix C.

## Appendix A ϵ italic-ϵ \epsilon italic_ϵ -approximate centroid set

The algorithm of constructing an $\epsilon$-approximate centroid set is proposed by Matoušek []. Here we briefly introduce the idea.
First, we use a quadtree to partition the space into hierarchical cubes. At each level of the tree, we construct a grid. The length of the grid is set to ensure that the grid points can always cover all approximate centroids of all cubes at this level. The approximate centroid set is the union of all grid points across all levels.

In Figure 3, we visually illustrate the difference between the $k$-means clustering center and the fair $k$-means clustering center.
The vanilla $k$-means induces a Voronoi diagram, so that every $k$-means center is located at the centroid of a $k$-means cluster. However, a fair $k$-means center can be located at the centroid of any potential cluster that satisfies the fairness constraints. The $\epsilon$-approximate centroid set structure can help us to find these potential centroids and preserves the fairness constraints for the later procedures.

Figure: Figure 3: The difference between the location of $k$-means clustering centers and the fair $k$-means clustering centers. The input dataset contains 3 different groups represented by orange, blue, and green points respectively. The red diamonds represent the cluster centers under different assumptions for the clustering problem. (a) shows the clustering result of $k$-means, while (b) shows the clustering result of fair $k$-means.
Refer to caption: extracted/5972673/centroid.png

## Appendix B Omitted Proofs

#### Theorem 2

If $T$ is
an $\epsilon$-approximate centroid set
of $\cup_{i=1}^{m}P^{(i)}$, Algorithm 1 returns a $(1+4\rho+O(\epsilon))$-approximate solution for $k$-sparse Wasserstein Barycenter problem.

To prove this theorem, we need the following lemmas.

###### Lemma 6 .

If $T$ is
an $\epsilon$-approximate centroid set
of $\cup_{i=1}^{m}P^{(i)}$ and $w(t)$ for each $t\in T$ is obtained by solving LP(2), then $T$ is a $(1+O(\epsilon))$-approximate Wasserstein Barycenter.

###### Proof.

A critical fact is that there exist an optimal Wasserstein Barycenter $T^{*}$ such that all points of $T^{*}$ located in the centroid of some fairlet of $P$. This claim has been proved in [Anderes et al., ] (Section 2, Equation 4). Therefore, if we calculate an $\epsilon$-approximate centroid set $T$, then $T$ can always cover the locations of $T^{*}$, *i.e.*, $\mathtt{Cost}(P,T,\phi^{*}_{T})\leq(1+O(\epsilon))\mathtt{Cost}(P,T^{*},\phi^{
*}_{T^{*}})\leq(1+O(\epsilon))OPT$. So using the same proof idea with Lemma 2, we can obtain the conclusion of Lemma 6.
∎

Combine Lemma 6 and Lemma 1, we arrive at Theorem 2.

###### Lemma 6 .

###### Proof.

## Appendix C The Rounding Technique

Our rounding algorithm consists of three steps: constructing a network structure of Minimum Cost Circulation Problem (MCCP), setting the parameters of each edge based on a fractional solution obtained by Algorithm 1, and solving the MCCP above. This reduction to MCCP is inspired by Ding and Xu [] (Section 4.3), while having some fundamental differences with their method. Our algorithm has different objectives compared to theirs, as it is based on a different approach to setting network parameters, and our method offers better time complexity guarantees. Our rounding algorithm requires only a single call to the minimum-cost circulation algorithm, and it can be completed in $O(n^{3}k^{2})$ time even when using the vanilla Edmonds-Karp algorithm [Dinitz, , Edmonds and Karp, ].

The process of our algorithm is described as follows. Recall that the dataset $P$ consists of $m$ different groups, *i.e.*, $P=\cup_{i=1}^{m}P^{(i)}$ and we assume that the groups are disjoint. By executing the Algorithm 1, we obtain a center set $S$ and corresponding fractional assignment matrix $\phi^{*}_{S}$. Now, in order to build a minimum cost circulation instance, we need to construct a network structure as Figure 4 and for each arc $(u,v)$, we should set the lower/upper bound of the flow $f(u,v)$ and its cost $c(u,v)$. We create a copy of $S$, denoted by $S^{(i)}$, for each group $P^{(i)}$. Each $S^{(i)}$ is a ”hub” used for transit, specifically to receive weights from group $P^{(i)}$ and transmit them to $S$. To facilitate understanding, we can imagine that each $s_{l}^{(i)}\in S^{(i)}$, where $l\in[k]$,
and its corresponding $s_{l}\in S$ are in the same position, but only accepts the weights from group $P^{(i)}$.
We set $c(p_{j}^{(i)},s_{l}^{(i)})$, *i.e.,* the cost of the arc from any $p_{j}^{(i)}\in P^{(i)}$, where $j\in[n^{(i)}]$, to an $s_{l}^{(i)}\in S^{(i)}$ to be $||p_{j}^{(i)}-s_{l}^{(i)}||^{2}$. The cost of the remaining arcs are 0 0.

Figure: Figure 4: The instance of the minimum cost circulation problem established through $(S,\phi_{S}^{*})$. The upper and lower bounds of the flow for each arc are annotated in the graph.
Refer to caption: extracted/5972673/fig-MCCP.png

Next, we set the lower bound and the upper bound of the flow on each arc, as shown in Figure 4.
First, the flow from the ”Source” node to each $p\in P$ is restricted to $1$, which means that each point $p\in P^{(1)}$ has a weight of $1$ to assign to $S^{(1)}$. Then, between each $P^{(i)}$ and its ”hub” $S^{(i)}$, the flow from each $p_{j}^{(i)}\in P^{(i)}$ to each $s_{l}^{(i)}\in S^{(i)}$ is bounded by $[0,1]$. Here, the flow $f(p_{j}^{(i)},s_{l}^{(i)})$ denotes the amount of the weight that assigned from $p_{j}^{(i)}$ to $s_{l}\in S$ in an $(\alpha,\beta)$-fair $k$-means solution. Subsequently, recall that in the solution $(S,\phi^{*}_{S})$ we obtained before, the weight received by a center $s_{l}\in S$ from group $P^{(i)}$ is $w^{(i)}(s_{l})$. We bound the flow $f(s_{l}^{(i)},s_{l})$ by $\big{[}\lfloor w^{(i)}(s_{l})\rfloor,\lceil w^{(i)}(s_{l})\rceil\big{]}$.
Finally, the flow from each $s_{l}\in S$ to the ”Sink” node is bounded by $\big{[}\lfloor w(s_{l})\rfloor,\lceil w(s_{l})\rceil\big{]}$, and we set $f(Sink,Source)=n$ to form a circulation. At this point, we have established an instance of the minimum cost circulation problem, denoted by $MCCP(S,\phi^{*}_{S})$. Obviously, we have the following observation:

###### Observation 1 .

$\phi^{*}_{S}$ induces a feasible solution of $MCCP(S,\phi^{*}_{S})$.

The observation is straightforward because the flow induced by $\phi^{*}_{S}$ meet all the bounds applied to the flow. Then, we give the proof of Lemma 4 mentioned in Section 3.1.

###### Observation 1 .

#### Lemma 4 .

There exists an algorithm that can round a fractional solution of $(\alpha,\beta)$-fair $k$-means to integral with at most $2$-violation while the cost does not increase.

###### Proof.

It is known that the minimum cost circulation problem has an integrality property [Cormen et al., ], which guarantees that if the arcs have integer capacities, there will always be an optimal solution with integer flow values on each arc. Utilizing an algorithm for minimum cost circulation problem or minimum cost flow problem (the two problems are equivalent), which converges to an integer solution like Ford-Fulkerson [Ford and Fulkerson, ], we can obtain an integer optimal solution of $MCCP(S,\phi^{*}_{S})$, which has a cost no larger than the solution induced by $\phi^{*}_{S}$.

Next, we prove that the assignment matrix, say $\phi^{\prime}_{S}$, induced by the integer optimal solution of $MCCP(S,\phi^{*}_{S})$ is a 2-violation assignment from $P$ to $S$.
Recall that we presented the definition of the violation factor in Section 2: An assignment matrix $\phi_{S}$ is a $\lambda$-violation solution if $\beta_{i}\sum_{p\in P}\phi_{S}(p,s)-\lambda\leq\sum_{p\in P^{(i)}}\phi_{S}(p,s
)\leq\alpha_{i}\sum_{p\in P}\phi_{S}(p,s)+\lambda,\quad\forall s\in S,\forall i
\in[m]$. According to the construction procedure of $MCCP(S,\phi^{*}_{S})$, the lower bound of the flow $f(s_{l}^{(i)},s_{l})$ is $\lfloor w^{(i)}(s_{l})\rfloor$, which satisfies:

$$ $\displaystyle\lfloor w^{(i)}(s_{l})\rfloor$ $\displaystyle\geq\lfloor\alpha^{(i)}(\lceil w(s_{l})\rceil-1)\rfloor$ (13) $\displaystyle=\lfloor\alpha_{i}\lceil w(s_{l})\rceil-\alpha_{i}\rfloor$ $\displaystyle\geq\lceil\alpha_{i}\lceil w(s_{l})\rceil-\alpha_{i}\rceil-1$ $\displaystyle\geq\big{(}\alpha_{i}\lceil w(s_{l})\rceil-\alpha_{i}\big{)}-1.$ $$

Note that the upper bound of the flow $f(s_{l},Sink)$ is $\lceil w(s_{l})\rceil$ so we have:

$$ $\displaystyle\lfloor w^{(i)}(s_{l})\rfloor$ $\displaystyle\geq\alpha_{i}\lceil w(s_{l})\rceil-\alpha_{i}-1$ (14) $\displaystyle\geq\alpha_{i}\lceil w(s_{l})\rceil-2,$ $$

and similarly,

$$ $\displaystyle\lceil w^{(i)}(s_{l})\rceil$ $\displaystyle\leq\beta_{i}\lfloor w(s_{l})\rfloor+\beta_{i}+1$ (15) $\displaystyle\leq\beta_{i}\lfloor w(s_{l})\rfloor+2,$ $$

which indicates that $\phi^{\prime}_{S}$ is a 2-violation assignment and complete the proof of Lemma 4.
∎

###### Proof.

## Appendix D Fixed Support Wasserstein Barycenter

Given $m$ discrete distributions (weighted point sets, each set has total weight sum to $1$) $P^{(1)},\cdots,P^{(m)}$ and a $k$ locations set $T$ of WB, the objective of fixed support WB as follows:

$$ $\displaystyle\begin{aligned} \min_{x}\quad&\frac{1}{m}\sum_{l=1}^{m}\sum_{i=1} ^{n^{(i)}}\sum_{j=1}^{n^{(j)}}\|P^{(l)}_{i}-T_{j}\|^{2}x^{(l)}_{ij}\\ s.t.\quad&\sum_{j=1}^{k}x^{(l)}_{ij}=1,\quad\forall l\in[m],\forall i\in[n^{(l )}]\\ &\sum_{i=1}^{n^{(l)}}x^{(l)}_{ij}w(P^{(w)}_{i})=y_{j},\quad\forall l\in[m], \forall j\in[k]\\ &\sum_{j=1}^{k}y_{j}=1,\\ &x^{(l)}_{ij}\geq 0,\quad\forall l\in[m],\forall i\in[n^{(l)}],\forall j\in k \\ &y_{j}\geq 0,\quad\forall j\in k\end{aligned}$ (16) $$

It is easy to see that fixed support WB problem can be solved using linear programming method. Several existing works on solving LP (16) including [Claici et al., , Cuturi and Doucet, , Cuturi and Peyré, , Lin et al., ].

## Appendix E Supplementary Experiment

### E.1 Datasets

The detailed information of our datasets is shown in Table 2. The group partition of every dataset is based on the “Group Column”. Every group column has some group values. The set of groups is the Cartesian product of group values of all group column. For example, the groups of Bank dataset are (married, yes), (married, no), (single, yes), (single, no), (divorced, yes), (divorced, no). For large dataset Census and Creditcard, we sample 1000 points to make sure the LP solver works in acceptable time.

**Table 2: Detailed Datasets Information**
| Dataset | Size | Dimension | Group Column | Groups Values |
| --- | --- | --- | --- | --- |
| Bank | 9999 | 3 | marital | married, single, divorced |
|  |  |  | default | yes, no |
| Adult | 4522 | 5 | sex | female, male |
|  |  | race | Amer-ind, asian-pac-isl, |  |
|  |  |  |  | black, other, white |
| Creditcard | 30000 | 5 | marriage | married, single, other, null |
|  |  |  | education | 7 groups |
| Census1990 | 50000 | 12 | dAge | 8 groups |
|  |  |  | iSex | female, male |
| Moons | 200 | 2 | color | 2 groups |
| Hypercube | 200 | 3 | color | 2 groups |
| Complex | 3032 | 2 | color | 9 groups |
| Cluto | 10000 | 2 | color | 8 groups |
| Breastcancer | 570 | 31 | label | 2 groups |
| Biodeg | 1055 | 40 | label | 2 groups |

### E.2 Comparison on Cost with different k 𝑘 k italic_k and ( α , β ) 𝛼 𝛽 (\alpha,\beta) ( italic_α , italic_β )

In the main paper, we set $\alpha_{i}=\beta_{i}=\frac{|P^{(i)}|}{|P|}$. Here, we try different $\alpha$ and $\beta$ to compare our algorithm to baselines. In order to make sure that the values of $\alpha$ and $\beta$ are feasible, we introduce the parameter $\delta\in(0,1)$, which represents the degree of relaxation of fairness constraints, with a larger $\delta$ indicating looser constraints. We set $\alpha_{i}=\frac{|P^{(i)}|}{|P|}\cdot\frac{1}{1-\delta}$ and $\beta_{i}=\frac{|P^{(i)}|}{|P|}\cdot{(1-\delta)}$. We set $\delta=0.1$ and $0.2$ to compare the cost
with baselines. The results are shown in Figure 5 and Figure 6, respectively.

In fact, as $\delta$ increases, the fairness constraints of the $(\alpha,\beta)$-fair $k$-means problem become more relaxed, and the corresponding fair $k$-means problem approaches the vanilla $k$-means problem. In cases where $\delta$ is large, in each cluster, the legal range of points from each group is larger, making the protection of fairness constraints less important, thus resulting in the optimal fair $k$-means center positions being very close to the centers of vanilla $k$-means. In the Table 2 of [Böhm et al., ], it is mentioned that when $\delta=0.2$, the clustering results of vanilla $k$-means only violate the fairness constraints by 0.4%-2%, which makes our algorithm less advantageous under a relatively relaxed $\delta$ value.

Figure: Figure 5: Comparison on Clustering Cost with $\delta=0.1$
Refer to caption: extracted/5972673/delta_1.png

Figure: Figure 6: Comparison on Clustering Cost with $\delta=0.2$
Refer to caption: extracted/5972673/delta_2.png

### E.3 Comparison on Cost of k 𝑘 k italic_k -sparse Wasserstein Barycenter

We compare our algorithm with the very recent work [Yang and Ding, ] (denoted by IJCAI24) who obtain $(2+\sqrt{\rho})^{2}$-approximate solution of $k$-sparse WB. The results are shown in Figure 7. In most cases, our algorithm can achieve a 10%-30% cost advantage over the previous work.

Figure: Figure 7: Comparison on the Cost of $k$-sparse Wasserstein Barycenter
Refer to caption: extracted/5972673/wb.png

### E.4 Cost on Different sampling ratio

In our algorithm, the most time consuming step is to solve LP(2) on $T$. A key observation during our experiment is that, after solving LP(2) on $T$, a large amount of points of $T$ have weight of 0 0. Therefore, it is possible to reduce the size of $T$ while maintain the quality of $T$. Meanwhile, smaller $T$ helps to reduce the running time. In order to verify our thoughts, we use sampling method after we obtain $T$. We use sampling ratio of $100\%$, $50\%$, $20\%$ and $10\%$ and calculate the final cost of Algorithm 1 with different $k$. The results are shown in Figure 891011. In these figures, we can see that in most cases, the cost of sampled $T$ do not increase too much (50% sample yields no more than 10% cost increasing and even 10% sample yields no more than 20% cost increasing in most cases).

### E.5 Running time with different sampling ratio on T 𝑇 T italic_T

As we discussed in E.4, sampling on relaxed solution $T$ can reduce the running time while the overall cost not increasing too much. We also test the running time with different sampling ratio. In summary, the running time of solving LP(2) on $T$ and overall Algorithm 1, shown in Table 3 and Table 4, can be significantly reduced by sampling.

**Table 3: Time (seconds) of solving LP(2) on $T$ with different sampling ratio**
| Dataset | 100% | 50% | 20% | 10% |
| --- | --- | --- | --- | --- |
| Bank | 39.97 | 19.14 | 7.12 | 3.39 |
| Adult | 66.48 | 28.58 | 9.67 | 4.64 |
| Creditcard | 80.235 | 32.51 | 11.08 | 5.43 |
| Census | 76.46 | 37.78 | 13.96 | 6.64 |
| Moons | 3.75 | 1.89 | 0.68 | 0.33 |
| Breastcancer | 11.03 | 5.28 | 2.01 | 1.07 |
| Cluto | 192.57 | 91.72 | 36.03 | 18.18 |
| Complex | 49.70 | 24.74 | 9.11 | 4.54 |

**Table 4: Overall time (seconds) with different sampling ratio of $T$ when $k=20$**
| Dataset | 100% | 50% | 20% | 10% |
| --- | --- | --- | --- | --- |
| Bank | 42.03 | 21.20 | 9.16 | 5.44 |
| Adult | 69.19 | 31.24 | 12.31 | 7.34 |
| Creditcard | 83.42 | 35.62 | 14.20 | 8.57 |
| Census | 80.23 | 41.62 | 17.86 | 10.48 |
| Moons | 4.07 | 2.15 | 0.97 | 0.60 |
| Breastcancer | 11.78 | 6.05 | 2.68 | 1.67 |
| Cluto | 201.54 | 100.64 | 45.82 | 27.74 |
| Complex | 52.23 | 27.25 | 11.66 | 7.05 |

Figure: Figure 8: The cost on centriod set $T$ with different sampling ratio when $k=5$
Refer to caption: extracted/5972673/sample_0.png

Figure: Figure 9: The cost on centriod set $T$ with different sampling ratio when $k=10$
Refer to caption: extracted/5972673/sample_1.png

Figure: Figure 10: The cost on centriod set $T$ with different sampling ratio when $k=15$
Refer to caption: extracted/5972673/sample_2.png

Figure: Figure 11: The cost on centriod set $T$ with different sampling ratio when $k=20$
Refer to caption: extracted/5972673/sample_3.png

### E.6 Experiments of Our Rounding Algorithm

In this section, we implement our rounding algorithm in Appendix C and compute the violation factor across different datasets and parameters. For convenience, we parameterize $\alpha_{i}$ and $\beta_{i}$ for the $i$-th group using a single parameter $\delta$. Specifically, we set $\beta_{i}=\frac{|P^{(i)}|(1-\delta)}{|P|}$ and $\alpha_{i}=\frac{|P^{(i)}|}{|P|(1-\delta)}$. Generally speaking, the smaller the $\delta$, the stricter the fairness constrains are. In Table 5 6 7, the violation introduced by our rounding algorithm is less than 1 in most of the cases and never exceeds 2, which aligns with our theoretical analysis.

**Table 5: Violation factor of our rounding algorithm with different $k$ ($\delta=0$)**
| dataset | 2 | 4 | 6 | 8 | 10 | 12 | 14 | 16 | 18 | 20 | 25 | 30 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Moons | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| Hypercube | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| Complex | 0.82 | 0.89 | 0.5 | 0.83 | 0.96 | 0.95 | 0.87 | 0.95 | 0.91 | 0.85 | 0.80 | 0.89 |
| Cluto | 0.80 | 0.86 | 0.72 | 1.01 | 1.04 | 0.94 | 1.0 | 1.02 | 0.90 | 0.90 | 1.1 | 0.9 |
| Biodeg | 0.05 | 0.66 | 0.65 | 0.63 | 0.64 | 0.62 | 0.63 | 0.68 | 0.77 | 0.79 | 0 | 0.01 |
| Breastcancer | 0.33 | 0.34 | 0.13 | 0.69 | 0.87 | 0.90 | 0.35 | 0.94 | 0.78 | 0.76 | 0.76 | 0.18 |

**Table 6: Violation factor of our rounding algorithm with different $k$ ($\delta=0.1$)**
| dataset | 2 | 4 | 6 | 8 | 10 | 12 | 14 | 16 | 18 | 20 | 25 | 30 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Moons | 0 | 0.3 | 0.35 | 0.40 | 0.30 | 0.40 | 0.70 | 0.5 | 0.35 | 0 | 0.20 | 0.40 |
| Hypercube | 0 | 0.94 | 0.98 | 0.94 | 0.83 | 0.95 | 0.85 | 0.91 | 0.80 | 0.88 | 1.02 | 0.83 |
| Complex | 0.67 | 0.98 | 0.66 | 0.87 | 0.88 | 0.97 | 0.76 | 0.77 | 0.89 | 0.97 | 0.67 | 1.03 |
| Cluto | 0.38 | 1.05 | 0.99 | 0.83 | 0.96 | 0.94 | 0.95 | 0.93 | 0.94 | 0.91 | 0.57 | 0.99 |
| Biodeg | 0 | 0.01 | 0.33 | 0.79 | 0.38 | 0.37 | 0.59 | 0.38 | 0.78 | 0.51 | 0.78 | 0.80 |
| Breastcancer | 0.18 | 0.23 | 0.40 | 0.23 | 0.39 | 0.89 | 0.53 | 0.33 | 0.47 | 0.51 | 0.34 | 0.68 |

**Table 7: Violation factor of our rounding algorithm with different $k$ ($\delta=0.2$)**
| dataset | 2 | 4 | 6 | 8 | 10 | 12 | 14 | 16 | 18 | 20 | 25 | 30 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Moons | 0 | 0.20 | 0.40 | 0.40 | 0.40 | 0.40 | 0.60 | 0.60 | 0.40 | 0.40 | 0.60 | 0.80 |
| Hypercube | 0 | 0.56 | 0.69 | 0.88 | 0.90 | 1.125 | 0.80 | 0.91 | 0.90 | 0.97 | 0.90 | 0.90 |
| Complex | 0.92 | 1.02 | 0.92 | 0.768 | 0.96 | 1.01 | 0.95 | 0.79 | 0.88 | 0.90 | 1.04 | 1.01 |
| Cluto | 0.85 | 0.90 | 0.90 | 0.88 | 0.83 | 1.024 | 0.85 | 0.86 | 0.90 | 0.88 | 0.96 | 1.00 |
| Biodeg | 0 | 0.50 | 0.56 | 0.39 | 0.51 | 0.69 | 0.19 | 0.57 | 0.56 | 0.64 | 0.75 | 0.65 |
| Breastcancer | 0 | 0.26 | 0.42 | 0.26 | 0.69 | 0.39 | 0.29 | 0.67 | 0.80 | 0.81 | 0.85 | 0.68 |

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
questions: 1) Is it possible to obtain fair $k$- clustering without any fairness violation without the requirement of equally sized groups? 

2) Can the method be extended to other clustering costs like $k$-median? It appears that proofs rely heavily on the cost being squared Euclidean distance.

3) Can you clarify how the solution to the k-sparse Wasserstein barycenter solution is guaranteed to be a distribution? Is the optimization slightly changed?
soundness: 3
strengths: 1) Fairness in clustering has gained a lot of attention in the past decade or so. For the case of $(\alpha, \beta) $ - fair clustering, the paper provides better approximation ratios than the existing works. 

2) The paper for the most part is written very nicely and is not difficult to follow the central ideas. Sufficient Proof sketches/ details are provided in the main part of the paper. Although I could not check all the proofs in details, the paper appears technically sound.

3) The paper also shows the effectiveness of the proposed algorithms by empirical results on different datasets. Some of the empirical results can be better presented (see weaknesses) but overall, it is a very good mix of theory and practice and very suitable for the venue.

4) The high-level idea of considering fairness while choosing the location of centers and not after choosing centers might give insights to design better algorithms other fairness definitions also.
summary: $ (\alpha, \beta) $ -fair k-means clustering is a group-based notion of fairness where the number of points belonging to each protected 'group' (race, gender etc.) inside each cluster is bounded. The paper provides algorithms for $ (\alpha, \beta) $ -fair k-means clustering and strictly $ (\alpha, \beta) $ -fair k-means clustering that have better approximation ratios than existing works. This is achieved by considering the group-based fairness constraints before choosing the location of the centers rather than first choosing centers and then trying to assign points to centers according to fairness constraints.  The paper also gives approximation guarantees for $k$- Sparse Wasserstein Barycenter problem that tries to find an 'average' distribution with a support size of $k$, for given discrete $m$ distributions, by treating the problem as a special case of fair clustering.  The theoretical results are supported by empirical evaluations.
weaknesses: 1) There is time complexity analysis of algorithm 1. However, there can be a comparison with the Bera et al. and Bohm et al. papers to get an idea of the tradeoff between approximation factor and time complexity. Empirical results should also result the time parameter. There are some experiments in the appendix, but they are just for your algorithm. Same goes for the violation ratio. 

2) In terms of presentation, I think, it would be better to move some experiments to the main paper and one more proof to the appendices.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: Q1: It seems that the proposed Relax-and-Merge framework is designed specifically for the Euclidean space. However, many fair algorithms can also be used to solve the case when data points are in a general metric space. Can the proposed method achieve better performances in general metric spaces compared with other fair clustering algorithms？

Q2: Since the $\epsilon$-approximation centroid set construction method does not rely on a specific constraint during the clustering process, whether the proposed framework can be extended to solve other fair clustering problems using $\epsilon$-approximation centroid set construction method? 

Q3: In the experimental parts, the authors only compare the clustering quality of the proposed algorithms with other fair clustering algorithms. Can the authors give a detailed comparison between the running time of the proposed framework and other existing fair clustering algorithms?

Q4: The clustering quality of the proposed algorithm rely heavily on the weighted algorithm used to reduce the number of partitions. However, in the experimental parts, there is no detailed description of which weighted algorithm is chosen and how the weighted algorithm is executed. Which weighted $k$-means algorithm is used in the experiments for Algorithm 1? Did the authors choose a PTAS for the experiments?
soundness: 3
strengths: The strength of this paper can be summarized as follows.

1. Fair clustering is a topic that receives much attention in machine learning. If equipped with a PTAS for the $k$-means problem, the proposed algorithm can achieve the best approximation ratio of $5+O(\epsilon)$, which improves the current state-of-the-art approaches on clustering quality guarantees.

2. The proposed Relax-and-Merge framework is simple and effective. The technical analysis proposed to bound the loss when reducing the number of partitions to exactly $k$ is interesting.

3. This paper is well-written and the proofs are easy to follow. 

4. The empirical evaluations demonstrate that the proposed framework achieves much better performances on clustering quality compared to the previous works.
summary: This paper studies the fair $k$-means clustering problem in Euclidean space, where the goal is to partition the given dataset into several groups such that each group should satisfy specific lower and upper bounds on the proportions of the assigned points. While the fair $k$-means clustering problem has been extensively studied in recent years, the existing approximation algorithms often incur at least a constant factor loss on the clustering quality guarantee in order to find good clustering centers for fair clustering instances that do not satisfy the “Voronoi properties”. To reduce the approximation loss, this paper introduces the notion of $\epsilon$-approximation centroid set, which can well approximate the locations for the optimal clustering centers under fairness constraints. Building on notion of the $\epsilon$-approximation centroid set, this paper proposes a Relax-and-Merge framework. The Relax-and-Merge framework first decomposes the given clustering instance into smaller partitions satisfying the fairness constraints (with more than $k$ partitions obtained) to construct a weighted instance. Then, by executing a weighted standard $k$-means algorithm on the weighted instance constructed, a solution satisfying the fairness constraints can be obtained  using linear programming rounding method, with better approximation guarantee on the clustering quality. Additionally, this paper shows that the proposed framework can also be extended to solve the $k$-sparse Wasserstein barycenter problem and strictly fair $k$-means problem. The experiments show that the proposed Relax-and-Merge framework achieves better clustering cost compared with other fair clustering algorithms, which further demonstrates the effectiveness of the proposed methods.
weaknesses: The weakness of this paper can be summarized as follows.

1. The approximation guarantees of the proposed method rely on the approximation loss of the weighted algorithm used to reduce the number of partitions. Although many weighted algorithms (such as the local search algorithms) can achieve near-optimal clustering results in practice, the worst-case analysis rely on the use of a PTAS algorithm to achieve better approximation guarantees. 

2. The proposed $\epsilon$-approximation centroid set is designed specifically to the Euclidean space. It is unclear that whether such methods can be extended to the general metric spaces.

---

confidence: 5
contribution: 3
initial_rating: 8
presentation: 3
questions: 1. Can one extend the results to the fair $k$-median?
soundness: 3
strengths: 1. Improved approximation algorithms for an important problem.
2. The idea is simple but very useful.
3. Experiments show it is also promising for practice.
summary: This paper considers the Euclidean fair $k$-means problem. In fair $k$-means, the input data set $G$ is partitioned into $m$ groups $G_1,..,G_m$ and $2m$ numbers $\alpha_1,..,\alpha_m,\beta_1,...\beta_m$ such that $\forall i\in[m], 0\leq \alpha_i\leq \beta_i\leq 1$. The task is to find $k$ clustering centers and partition $G$ into $k$ clusters so that for every $i\in [k],j\in [m]$ cluster $P_i$ must contain at least $\alpha_j|P_i|$  points and at most $\beta_j|P_i|$ points from group $G_j$.

The main contribution of this paper is two improved approximation algorithms for fair $k$-means. The first algorithm shows one can compute a $1+4\rho+\epsilon$ approximation with constant violation in fairness constraints by running upon an existing $\rho$-approximation algorithm for vanilla Euclidean $k$-means. This algorithm also relies on a centroid of size $O(n\epsilon^{-d}\log \epsilon^{-1})$ thus the running time is exponential on $d$. The second algorithm is designed for the strictly fair $k$-means, namely $\forall i, \alpha_i=\beta_i=\frac{1}{m}$. A $ 2+6\rho$ approximation without violation is obtained. Both algorithms have better approximation ratios than previous results. The authors also observe that the first algorithm can be extended to a related problem called $k$-sparse Wasserstein Barycenter.

Technically, authors observe that one can first compute an optimal assignment from the data set to a centroid set and then reduce the problem to the vanilla $k$-means by assigning each data point to its center in the centroid set. The idea is simple but effective. Experiments also show improvement over previous results.

Overall, I think this paper reaches the acceptance bar.
weaknesses: 1. The running time of the first algorithm is exponential on $d$. Thus the result does not scale in high dimensions.
2. Eventually, the main contribution of this paper is a reduction via a centroid set. The performance relies on the centroid set construction algorithm and the approximation algorithm for vanilla $k$-means.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: Some questions can be found in the other part of review.
soundness: 3
strengths: - Fair clustering is a relevant problem, and the paper gives an approximation algorithm better than the known results in the Euclidean setting.
summary: The paper gives an approximation algorithm for the fair k-means algorithm, where, in addition to minimizing the sum of squared distances, the clusters should also satisfy certain minimum and maximum size constraints (stated as fractions of the data points). The paper gives (1+4c+O(\eps))-approximation algorithm with running time that has an exponential dependence on the dimension d and polynomial dependence on other parameters. The suggested algorithm first finds an \eps-centroid set T using Matousek's algorithm. This is followed by assigning points to centers in the set T by solving an LP that guarantees fairness. The size of T is exponential in dimension d. Since k centers need to be produced, the algorithm finds k centers by running a c-approximation algorithm for the vanilla k-means algorithm over points that are "moved" to their respective centers in T. Finally, integer assignments are found using ideas of Bera et al. (LP rounding), which causes minor violations in fairness conditions. This two-step process (clustering points using T followed by clustering T) is called Relax-and-Merge. Similar ideas have been used in the past (see, e.g., [A]), and the approximation analysis of the two-step process is similar to previous results (see Theorem 4 in [A]).

[A] https://theory.stanford.edu/~nmishra/Papers/clusteringDataStreamsTheoryPractice.pdf

Additional comment: I have reviewed an earlier version of the paper, and much of the review is from my earlier review. The current version improves the number of violations in the special case of mutually disjoint groups. This is shown by setting up an appropriate minimum-cost circulation problem.
weaknesses: - The centroid set-based algorithm is specific to the Euclidean setting and cannot be extended to general metric spaces.
- The exponential dependence of the running time on d may be problematic for high-dimensional data.
- The techniques have mainly been borrowed from previous works. So, the theoretical contribution has limited novelty. 
- PTAS for vanilla k-means either have exponential dependence on k or d. So, the ~ 5-approximation is at the cost of increasing the running time.

Meta-review: The notion of $(\alpha, \beta)$ fair clustering was introduced to consider $k$-means and other clustering algorithms with fairness constraints. The paper provides improved approximation algorithms for this problem and also the problem of $k$-sparse Wasserstein Barycenter. The results are interest and the paper has some algorithmic novelty; the results are also supported by empirical evidence.

Decision: Accept (Poster)