Relax and Merge: A Simple Yet Effective Framework for Solving Fair $k$-Means and $k$-sparse Wasserstein Barycenter Problems
Authors: Shihong Song
Guanlin Mo
Hu Ding
Venue: ICLR 2025 Poster (2025)
Keywords: clustering
k-means
fairness
approxiamte algorithm
optimal transport
Primary area: alignment, fairness, safety, privacy, and societal considerations
TL;DR: An improved algorithm for fair k-means problem.

Abstract: The fairness of clustering algorithms has gained widespread attention across various areas, including machine learning, In this paper, we study fair $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 optimal locations of $k$ centers is a quite challenging task. 
  We propose a novel ``Relax and Merge'' framework that returns a $(1+4\rho + O(\epsilon))$-approximate solution,  where $\rho$ is the approximate ratio of an off-the-shelf vanilla $k$-means algorithm and $O(\epsilon)$ can be an arbitrarily small positive number. If equipped with a PTAS of $k$-means, our solution can achieve an approximation ratio of $(5+O(\epsilon))$  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\rho +O(\epsilon))$-approximate solution for the $k$-sparse Wasserstein Barycenter problem, which is a fundamental optimization problem in the field of optimal transport, and a $(2+6\rho)$-approximate solution for the strictly fair $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.

Published as a conference paper at ICLR 2025
RELAX AND MERGE: A SIMPLE YET EFFECTIVE FRAMEWORK FOR SOLVING FAIR M-MEANS AND k- SPARSE WASSERSTEIN BARYCENTER PROBLEMS
Shihong Song, Guanlin Mo ; Hu Ding!
School of Computer Science and Technology. University of Science and Technology of China (shihongsong, Coguanlin]@maii .usucccc w.d.dd.ccc hudi budingeustc.com edu.
ABSTRACT
The faimess of clustering algorithms has gained widespread attention across var- ious areas machine learning. In this paper, we study fair k-means clustering in Euclidean space. Given a dataset comprising several groups, the fairness con- straint 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
centers and finding the induced partition are quite challenging tasks. We propose novel "Relax and Merge" framework that returns (1 + 4p + O()) -apprriapio solution, where p is the approximate ratio of an off- the-shelf vanilla k-means algorithm and (c)) can be arbitrarily small positive number. If equipped with a PTAS of k-means, our solution can achieve an approxi- mation ratio of (5 + O()) with only slight violation of the fairness constraints, which improves the current state-of-the-ee art approximation guarantee. Furthermore, -approxiiit solution for the k-sparse Wasserstein Barycenter problem, which is a fundamental optimization problem in the field of optimal transport, and a (2 + approxxixeee solution for the strictly fair k-means clustering with no violation, both of which are better than the current state-of-the-as methods. In addition, the empirical results demonstrate that our proposed algorithm can significantly outperform baseline approaches in terms of clustering cost.
using our framework, we can also obtain a (1+-pp+
INTRODUCTION
Clustering 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
al. 2014 Alelyani al. 2018 Yuan et al. 2023 Zhang et al., 2023). image processing (Coleman &
Andrews 1979 Chang et al. 2017). and biomformatics (Ronnn et al. 2016 Nugent & Mcila, 2010).
In particular, the k-means clustering problem has been extensively studied in the past decades (Jain) 2010). Given an input dataset P c Rdd the goal of the k-means problem is to find 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 al. 2017 Bera al. 2019 Huang al. 2019 Chen et al. 2019 Ghadiri et al. 2021)
In this paper, we consider the problem of ()-farr k-means clustering that initially proposed by Chierichetti et al. (2017) and then generalized by Bera et al.) (2019). Informally speaking, we assume that the given dataset P consists of m groups of points, and the "faimess" constraint requires that in each obtained cluster, the points from each group should take fraction between pre-specified lower and upper bounds. Bera et al. (2019) showed that p-approximate algorithm for vanilla
'The first two authors contribute equally.
1 'Correponndig author.

---

Published as a conference paper at ICLR 2025
k-means can provide (2 + 2 approximate solution for (a, 3)-fiir k-clustering with slight violation on the faimess constraints, where the "violation" " 15 formally defined in Section 2 Regarding the no violation scenario, Dai et al. (2022) and Wu et al. (2024) both obtained a (logk) -aprrxximate solution for fair k-median. Wu et al. (2024) achieved a quasi-polymomial--iin
approximate scheme. Furthermore, [Böhm et al. (2021) p 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
(2 + vp)² approximate solution without violation. These fair k-means algorithms can also be accelerated by using the coreset techniques, such as (Huang et al., [019 Braverman et al. 2022 Bandyapadhyay et al.) 2024). There also exist polynomial-ting -ime approximation scheme (PTAS) for fair k-means, such as the algorithms proposed in (Böhm et al. [021]] Schmidt et al. [2020] Baadyapadhyya (et al. 2024), 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 propertionally fair
clustering Chen et al., 2019; Micha & Shah 2020) and socially fair k-means clustering (Ghadiri
ct al. 2021 1
Abbasi al. 202 Makarychev & Vakilian| [021 Chlamtáë et al. 2022).
Another problemm closely related to fair k-means is the so-called "k-sparse Wassertein Barycenter (WB)" (Agueh & Carlier, 2011) (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 set of probability distributions. It plays crucial role in various applications such as image processing (Bonneel et al. [2015) Cuturi & Doucet, 2014), data analysis (Rabin et al., 2012). and machine learning (Backhoff- Veraguas al. [2022] Metelli et al., 2019). Given m > I discrete distributions, the goal of the k-sparse WB problem is to find a discrete distribution (i.c., the barycenter) that minimizes the sum of the Wasserstein distances (Villani 202T between itself to all the given distributions, and meanwhile the support size of the barycenter is restricted to be no larger than given integer & 2 1. If relaxing the "k-sparse" constraint (i.e., the barycenter is allowed to take support size larger than k). [lttchuler & Boix- 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. 22188 (Cuturi & Doucet, (2014) Cuturi & Peyré. 2016: Lin et al.) 2020). If keep the "k--sparse" constraint, it has been proved that the problem is NP-hard (Borgwardt & Patterson 202T). To the best of our knowledge, the current lowest approximation ratio of k-sparse WB problem is also (2 + vp)² (same with the aforementioned approximation factor for fair k-means), as recently studied by Yang & Ding (2024). 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 & Ding (2024) inspires us to consider solving the k-sparse WB problem under our framework.
(2021) presented an algorithm based on
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 -rt approximation qualities are still not that satisfying. The major difficulty arises from the lack of "locality property" (Ding & Xu 2020: Bhattacharya et al.) 2018) 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, k-means clustering implicitly forms a Voronoi diagram, where the cell centers are exactly the & 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. 2019 Böhm et al. 202T) 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 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.
In their paper, the approximate ratio is written as (2 + p) because they added a squared root to the k-means cost function.
2

---

Published as a conference paper at ICLR 2025
Our key ideas and main results. Our key idea relies on an important observation, where find that the fair k-mmans problem is inherently related to a classic geometric structure, "e-approximate centroid set", which was firstly proposed by Matousek (200). Roughly speaking, given dataset, an c-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 c-approximate centroid set contains not only the approximate centroids based on the Voronoi diagram, but also the approximate centroids of those potential cainees--preserving clusters.
Inspired by the above observation, we illustrate the relationship between fair k-means and e- approximate centroid set first, and then propose novel Relax-and-Merg 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 our result is better than the state of the art works (Bera et al. 2019 Böhm et al. (02T). Equipped with a PTAS for k-means problem (e.g., the algorithm from Cohen- Addad et al. (2019), ) our algorithm yields 5 + Oe)) approximation factor. We also present two important extensions from our work. The first extension an (1 + 4p + O(e)) 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 + 6p) approximation factor, which is better than the state of the work (Böhm al., 2021).
Approximation ratio
When
Algorithms
Note on the quality
P = 1 0
Bera et al. (2019)
(2 + vp)
O(c)
general case two groups only strictly only, no violation
Schmidt et 2202
5.5p+1
0(e+
Böhm et al.
2021)
(2 vp)
9+c(c)
Yang & Ding
(022))
(2 vp)
9+0(c
k-sparse WB general case strictly only, no violation
Algorithm
now
144p+0(1)
5+0())
Algorithm
now
6p
8 8+0(c)
Table I: Comparison of the approximation ratios for fair k-means and k-sparse WB, The "general case" includes (a:, fair k-means, strictly (a, Ba-rrir k-means and k-sparse WB.
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 & is large (Mahajan et al.] (012).. In high dimensions, even if k is fixed, say k 2, the k-means problem is still ha-hard (Drineas et al., 2004). Furthermore, Lee et al. (2017) 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 # NP. Therefore, a number of approximation algorithms have been proposed in theory. If the dimension is fixed, Kanungo et al. (2002) obtained (9 + Oppa--ppro 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, Johen-Addaa et al. (2019) and Friggstad et al. (2019) proposed the PTASeS for k-means low dimensional space (or high dimensional space with constant doubling dimension). For nigh-dimensional case with constant k, Kumar et al. (2010) proposed an elegant peeling algorithm that iteratively finds the cluster centers and eventually obtain the PTAS. In addition, simplified PTAS based on D sampling was later proposed by Jaiswal al. (0144)
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 Rd The set P consists of m different groups (not necessarily disjoint), i.e., P - p(t), p()), and each group has the size | = n (4) (we use the superscript "(i)" to denote the group's 's index). The Euclidean distance between two points b E Ad is denoted by ||a bll: the distance between point and any set Q c Rd is denoted by dist(a, Q) = minge ||a |I. and the nearest neighbor in Q is denoted A (a, Q). The centroid of set is denoted by Cen(Q).
3

---

Published as a conference paper at ICLR 2025
For the vanilla k- k-means problem, the client points are always assigned to their nearest center. However, the fairness constraint is considered, 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 Φs P x S + IR to indicate the assignment relation between the client points and cluster centers. For every p E P and (p, s) denotes the proportion that is assigned to center (c.g., we may respectively assign 30% and 70% to two different centers). Obviously, we have EeES Øs s) = 1. For each center E S, we use w(s) }} = Eper (p, s) to denote the amount of weight assigned to s; for each group p(),
S,
we similarly define the function (s) Eperis &s (p, s). Let Cost (P, S, (s) denote the cost of input instance P with given S and do:
Cost(P,8,
ΣΣ PEP
1p (l,))s())))
Problem 1 ((a, 3)-fair k-means clustering (Bera et al. 2019)). Given instance P as described above and two parameter vectors a. B E [0, T the goal of the (ox, f k-means clustering is to find the set S consisting of k points and assignment matrix Øs, such that the clustering cost 4 is minimized, and meanwhile each cluster center E S should satisfy the fairness constraint: Brw(s) S (s) S a,w(s) for every i E 11,2, m.]. Here, we use ai Bg denote the i-th entry of a and B, respectively.
Moreover, if the m groups are disjoint with equal size (i.e., n n/m for any i), and a; = B, 1/m for each group p(), we say this is a strictly fair k-means clustering problem.
For Problem [ we can specify two types of solutions: fractional and integral. Their difference is only from the restriction the assignment matrix és. For the first one, each entry (s s) can be any real number between 0 and 1; but for the latter one, we require that the value of Φs(p, 8) should be either 0 or 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. 2019) introduced the violation factor measure the violations of fairness constraints after rounding: an assignment matrix Φs is a X-violation solution if 3, Eper Φ3 (p, s)
< Epepos (p(p,s) s) S a; Epep Øs (p. s) + X, Vs E S, Vi E [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 denote the optimal integral cost of Problem | We use Sapt assignment matrix is denoted by S.n. For each šj. let C2 {p P @ (p. 8,) 0} be the corresponding cluster, i.e., the set of point assigned to it. A simple observation is that, if given
{ , to denote the optimal solution of integral fair k-means problem and its
fixed candidate cluster centers set S, the assignment matrix Φs can obtained via solving linear programming (we can view the x & entries of Øs as the variables):
min @5
ΣΣ lI (1,,s())
PEP
s.t.
B,
Σ (s(p,)) 8) Σ
os(p. Sa Σ os(p,s), Vs V [m],
(2)
PEP
PEP
PEP
Σ
(p. 11 P.
#ES
If we want to compute an integral solution, the above (2 should be an integer LP. Given set S, & denotes the optimal solution of ( and Φs denotes the corresponding optimal integral solution.
The following proposition is folklore result that has been used in many articles clustering algorithms (e.g.. (Kanungo et al., (002)). We will also repeatedly use it in our proofs.
Proposition Given a finite weighted point set Q C Rd for any point a. Eyeq w(q)] gll2 Egeq w(q)lle 11g Cen(Q)]1 + w(Q) ||a Cen 1?? where w(Q) is the total weight of Q.
Next we introduce an important geometric structure "c-approximate centroid set", which was firstly proposed by Matoušek| (2000). Roughly speaking, the e-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.
4

---

Published as a conference paper at ICLR 2025
Definition 1. Given finite set P R and small parameter > O. we use (P) denote e-approximate centroid set of P that satisfies: for any nonempty subset Q C P, there always exists a point (P) such that | Cen(Q)Il - / कि Eneq 114 (en
Remark Matoušek 2000 also presented a construction algorithm based on the space partitioning technique "quadtree" (Finkel & Bentley 1974). In Appendix A we briefty illustrate the role of the c-approximate centroid set in preserving fairness constraints and how to construct it. The size of the obtained e-approximate centroid set is O(IPle (e log(1/ (o)(1/)) and the construction time complexity is O(1 log P| + P|e log(1/e))
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 R Wasserstein distance is the minimum transportation cost between P and Q: W(P, Q)
minr v Epp Eyeq F(p. q)ppp -l1?, where the transport matrix F P Q [0, should satisfy: EperF(r F(p,q) w(q) for any q Q and EgEq F(p,9) w(p) for any p E P, where w(p) (or w(q)) is the weight of point p (or q) such that Epep w(p) Eyeq""! w(q)-
For weighted set S, we use sSpp(S) to denote its support, i.e., the set that shares the same location of S but not weighted. The number of points is (Sp is denoted by (upp((S)]
Problem 2 (k-sparse Wassertein Barycenter (k-sparse WB)). Given m discrete probability distri- butions p()). ..... pim) supported on R", WB the probability distribution S minimizing the sum of squared Wasserstein distances to them, i.e, arg ming > k-sparse Wasserstein Barycenter if we restrict [supp(S)]
m i== (²(P(), ( The problem is called
In Section 3.2 we explain why this problem can be regarded as fair k-means clustering.
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 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 centers, and then take the fairness into account in the second stage (Bera et al. 2201)] Böhm et al.) 2021). 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 instance of Problem 7 and a p-approximate vanilla k-means clustering algorithm, there exists an algorithm that can return a fructional (1 + 4p O())) approximate solution for Problem ! Further, one can apply rounding method transform this fractional solution to an integral one with constant violation factor while ensuring the cost does not increase.
The details for computing the fractional solution are shown in Algorithm || The set T in the relax stage contains the approximate centroids of all the potential clusters with preserving fair constraints. Then we solve linear program to obtain the relaxed solution (T, (+) that also preserves the fair constraints. Because of that, the merge stage is able determine the appropriate locations for the cluster centers of Problem
3.1 DETAILS FOR (a, 3) FAIR k-MEANS ALGORITHM
First, we mainly focus on the fractional version of (ax, 3a-r k-means problem. More precisely, we allow the value of the assignment function &s to be real number in [0. 1 rather than 1). To prove Theorem [ we need the following lemmas first. Specifically, Lemma D provides the bound for the cost from the merged solution S; Lemma 2 shows that the e-approximate centroid set provides satisfied relaxed solution with a cost no more than (1 + OPT) Combining with the rounding methods, Theorem can be obtained.
Lemma 1. Let nj be any positive number. we suppose Cost(P,T, Φ7) S 11-10O1 OPT, then the solution (S, )3)) returned by Algorithm / is an (17 (2n + 2)p) -approximate solution for Problem 7
5

---

Proof. According the definition of fractional fair k-means problem, the cost can be written as Published as a conference paper at ICLR 2025
Algorithm 1: FRACTIONAL. FAIR K-MEANS
Input: The dataset P, k, a, 3. and
Relax: Construct relaxed solution T. Le., an e-approximate centroid set, such that Cost( T, (r-) S (1 + (()) OPT (see Lemma P Here, we relax the size constraint of centers to be polynomial of n rather than exactly k, as achieve sufficiently low cost. Solve LP (2) on T to obtain the optimal assignment matrix 07. T and ΦT can be viewed as a relaxed solution for (a, -firr k-means, i.e,, the number of centers may be more than k, and meanwhile, the cost bounded and the faimess constraints are also preserved.
Adjust T. For each E T, update the location of t to be the corresponding cluster centroid
x(t) Σpep (w.0) The adjusted T is denoted by TTT).
((t)
Merge: Run a p-approximate k-means algorithm on π (T²) to obtain centers set S. Then, solve LP (2) on S obtain the optimal assignment matrix 45.
return S and 05
Cost(P,S.0š) = ΣΣ 1 s| (p,
PEP
Now we consider another assignment strategy: we firstly assign P to T according to or (recall that or the optimal fractional assignment matrix from P to 7), and then we assign every weighted point in T' to some S such that is closest point to (tt). Since o3 is the optimal assignment matrix from P to S, the cost of this assignment strategy should have:
ΣΣ 1 ((T()) S)II (p, Co))(
PEP
Since Tf) is the centroid of the weighted points assigned to t, according to Proposition we know the left-hand side of (4) should have the upper bound
Σ
lp x (1 + [T((t) (Tt(().
IET
PEP
ΣΣ PEP
lp (+)| (p. +
[t) - (m)(
(5)
EE
(
(b)
Then we bound (a) and (b) separately.
(a) -h
EE Sn OPT. PEPIET
(6)
PEP
The first inequality holds because (t) is the centroid of the weighted points assigned to f, minimizing the weighted sum of the squared distances between them. The second inequality holds because
Cost(P, P. T, (7,) < n- OT. Next, we focus on (b). Suppose Smeans is the optimal k-means solution of π (T). Then we have:
(b)
Σ [(()) - ((T((),))
Σ [T((1) (N(((())) (l)
((() (I) (1
Σ [|=(t)= ((((()) S Smeans)) S5p (p. (p (p)
=
PEP TET SES
<P ΣΣ Σ [T((t) $1 (p. 3) (p.
PEP FET SESupt

---

Published as a conference paper at ICLR 2025
The first inequality holds because of the p-approximate k-means algorithm. The second equality holds because for every t E T, Epep @7 (p, t) = w(t). The third equality holds because for every E P. Eies.pr Sag (p, 3) = 1. And the last equality holds because of the optimality of Smeans. Further, according to squared triangle inequality, we have
(b) - ΣΣ
Σ
[|((() - pll + 11p1 511'00s.p (o. 8) ()().))
PEP IET
Spp
(1| - p (p,
PEr 1ET Sppt
(8)
E
2|p- B| SSpr (p, (1,)
p
PEP TET SESppt
2p
ΣΣ PEP EET
[T(()
25 (p, +) 2p Σ Σ
1|p- 31120' S (p, 3).
PEP Sept
The last equality holds because for any p E P. Eiesop Sop (p, 1. The first term is exactly 2p times (a) and the second term equals 2p- OPT. Through combining (a) and (b), we can obtain an approximation factor of + (2n + p)p.
Algorithm| D reduces the fair k-means problem to computing the set T. The following lemma shows that an e-approximate centroid set is a good candidate for T,.
Lemma 2. I is an e-approximate centroid set of P. then Cost(P,T,, o7) S (1 + O(e))OPT
Proof. According to Definition let it E T denote the point such that ||t; - Cen Cen(Cr) (C²)ll S C. Epec; lp- - Cen(C,))l where Cj is the j-th optimal cluster. Let T" = {tl ... .tx]. A key observation is that each optimal center 3y is always the centroid of C2, i.e., cen 3j. so we have It, (C,)(1 < 9|cy| Epec, ||p- 3y112 pic,007 where OPT, Epec, ||p By
2²
If we assign all points of C3 to 1j. the cost of every Cj can be written as Epec, ||4 - 11
2²
Σ 1,11+ + Σ ll - 1 OPT, + = (1
(9)
9
PEC;
PEC₃
The first equality holds due to Proposition 1 Since क.. is the optimal assignment matrix of T', (1+ Σ OPT, (1+O()))PPT Finally, Cost(P, 2", o7-) S Σ5= Emec, -11² S
since T is a subset of T. we have (ost(P,TT) Φ7) S (o (T)) S (1 O())OOPT n
Through combining Lemma I and Lemma 2 we can immediately obtain Lemma S
Lemma 3. Equipped with the e-approximate centroid set by Matoušek 2000), the cost of the solution
returned by Algorithm| [ is at most (1 + 4p - O( Furthermore, by utilizing the PTAS of vanilla k-maans algorithm, the cost of the solution is at most (5 OPP)
Rounding for integral solution. Note that Lemma I only guarantees fractional solution. Recall the
"violation factor" introduced in Section 2 According the rounding method proposed in (Bera et al. 2019), a fractional solution of Problem can be rounded to be integral with (3A + 4) violation, where is the maximum number of groups a point can join in (c.g., if point can belong to three groups, A 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 new rounding method that can improve this violation factor to "2" when assuming A = 1, i.e., the groups are mutually disjoint, meaning that each point belongs to exactly one group (if using the method of (Bera et al. 2019). 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 ct al. (2019): Wu et al. (024); [Cheerichetti et al. (2017). Our key idea is building a "hub-guided" minimum cost circulation problem. Roughly speaking, we utilize set of carefully designed "hubs"
7

---

Published as a conference paper at ICLR 2025
in transportation network, for guiding the integral fair matching between the input points and the obtained cluster centers. We show the result in Lemmal4 and place the proof to Appendix C
Lemma 4. If the groups are mutually disjoint, one can round the fractional solution returned by Algorithm 7 to be integral with at most 2-violation, while the cost does not increase.
Finally, Theorem D can be obtained by combining either the rounding method from (Bera et al. 2019) for general case, or Lemma 4 for disjoint case.
Overall time complexity. As we mentioned in Remark I computing an e-approximate centroid set of P needs On log n + ne (og()/e)) time. Suppose the time complexities of linear programming. vanilla h-means are denoted by TI. and Tmeanss respectively. The time complexity of the adjustment of T is OnT)),, which is dominated by TI. because the size of oT is n (T). Therefore, the overall time complexity of Algorithm [ is On log n. + nnc- (1g((/))) + 'TL + Tieans- It is worth noting the the complexity can be further reduced by using the assignment preserving coreset ideas (Huang) et al. 2019 Braverman et al., 2022 Bandyapadhyay et al. 2024). By doing this, we need introduce an extra running time for coreset construction, which is linear to n, but we can compress the data size from n to (k) e).
3.2
EXTENSION TO A-SPARSE WASSERSTEIN BARYCENTER
cute property of Algorithm Dis that 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 barycenter, w()) (s) = 1 for any E [m]. Namely, we can directly perform our "Relax and Merge" framework by setting a; = 8; 1/m. First, we calculate the c-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., 2018: Cuturi & Doucet 2014, Cuturi & Peyré) 2016; [in et al.) (020) 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 to obtain the k-spar solution.
m (s))
Theorem 2. IfT is an c-approximate centroid set of U p(), Algoritim Sesoorittmrrtnnssss (1 O(c))-(())- approximate solution for k-spass Wasserstein Barycenter problem.
3.3 STRICTLY FAIR M-MEANS WITHOUT VIOLATION
Since the strictly fair k-means is special case of (a, -fair k-means, by using Algorithm I 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. (017) for the input groups and use its centroids as the relaxed solution T' rather than e-approxiamte centroid set. First, we give the definition of fairlet decomposition for multiple groups, which extends the original definition of (Chierichetti al. (017)) from two groups to multiple groups.
Definition (Fairlet Decomposition). Given a dataset P that has m equal-sized disjoint groups, We say set G of m points is a fairlet of P. if G contains exactly one point from each group of P. A set G nf/m fairlets is a fairlet decomposition of P, if all fairlets in G are disjoint, where n/m m is the number of points in each group of P.
We define the cost of fairlet decomposition G as Costrairier (9) = Epec lpp Cen(G)])
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 p-approximate vanilla h-means algorithm on these centroids. So, reduce the strictly fair k-means problem to the fairlet decomposition problem. We propose Algorithm [] which first computes a 2-approximate fairlet decomposition and then generates a (2 + approximxee integral solution for strictly fair k-means.
Theorem 3. Algorithm 2
returns (2 + 6p) aapproximaeee integral solution of strictly fair k-means.
To prove Theorem 3 we need to prove the following lemma, which shows that 9 is a 2-approximate fairlet decomposition. Then, we can use the same idea of Lemma [ to obtain Theorem 3 Recall
8

---

Published as a conference paper at ICLR 2025
Algorithm 2: STRICYTLY FAIR M-MAS
Input: The dataset P - p(), k
for i 1 t0 m do
j 1 and # do Compute the perfect one-to-one matching тú between p(() and p() (pairwise matching cost is the squared distance) by using the Hungarian algorithm (Kuhn 1955). For each point p E p(t), the point matched with p in pl) is denoted as (p)
end
Construct fairlet decomposition 93 (initially empty) according to the matchings: for each point p E p(t), add the fairlet (Ti (p), T2(P), "", (p)) (Tmm to G..
.end
Choose Gn where v = arg min; Eps p(s) Σ Ip - (>))( as G.
Construct the relaxed solution 7 {Cen G) G is any fairlet of g). Run p-approximate k-means algorithm on T. and obtain the solution S.
10 Integral assignment: Assign all the points according to the fairlet decomposition G, i.e., if point p belongs to some fairlet G, then assign p N (Cen(G), return S and the obtained integral assignment
that Lemma 1 shows that if have relaxed solution T with bounded cost v) OPT, then the merged solution will have constant approximate ratio. Here, T obtained by Algorithm 2 also provides relaxed solution whose cost does not exceed 20PT. Hence, after we merge T and obtain S, the approximate ratio should no more than (17 + (2n) + 2)p) = 2 + 6p. Furthermore, if we use PTAS for k-means, the overall approximate ratio of Algorithm 2 is 8 - O(c).
Lemma 5. IfG is the fairlet decomposition obtained by Algorithm then Cost (9) S 20PT.
Proof. Suppose G a fairlet, and we use G(O) to denote the point G and belongs to group p(),
i.e., (() is the unique point G p(1), Now we bound the Cost as follows:
Costsairtan (9)
lp Cen(G)]
GEG PEG
(10)
ΣΣ 1ppplpae Cen(G) PEG
Σ || Cen Geg
where is the "best" group index selected in Line 7 in Algorithm 2 We GoPT denote the optimal fairlet decomposition that has the lowest cost (we cannot obtain GoPT in reality, and here we just use for conducting our analysis). For each p E P, let GoPT(P) denote the fairlet of GoPT that p belongs to, i.e., p E GOPT(P). Suppose that p(u) is the "closest" group to GoPT i.e. u = arg minse[m] Epepor |[Cen(GoP(()) - plla. According to Proposition the right side of (10) equals to Eper(>) プラ= lpp
Tuj (p) 12, so have Cost fastfuircc(())
Σ Σ 1 PEP( j=1
Σ
Σ
lp Tp)11)
<
Σ PEP(N) j=1
Σ
1p (Gor(())) (11)
pEP(#)
The first inequality holds because v = arg min; Epepco E/=1 equality holds because 7 is the perfect one-to-one matching. Using Proposition T Tagain, we have Cost (astffrr))))) 5
Ilp (2) And the last in-
Σ
Σ (en(GGoP(p) - (GorT())) +m m Σ [[Cen(Gopr()) pl2. (12) PEP(s)
pEP(s) 1=1
Note that GoPT is the optimal fairlet decomposition, well as the optimal strictly fair n nem-means solution, so the first term of [1] should be most OPT. As for the second term, since p(w) the "closest" group to G, it should be no larger than m -/- LOPT - OPT (because the minimum distance "Epep(") [[Cen(GoPr()) complete the proof of Lemma
2 should not exceed the average distance -OPT). Overall, we

---

Published as a conference paper at ICLR 2025
4 EXPERIMENTS
In this section, we perform the empirical evaluation on our algorithms. Our experiments are conducted on 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, L.C 2023)). ). We use the following datasets which are commonly used in previous works: Bank (Moro et al. (412) points with groups), Adult (Becker & Kohavi (996) (32561
points with 7 groups), Census (Zhou & Chen (50000 points with 10 groups), creditcard (Ych) Lien 2009) (30000 points with 8 groups), Biodeg (Mansouri et al., 2013) (1055 points with 2 groups), Breastcancer (Wolberg, William, Vlangasarian,Olvi. Street, Nick, and Street, W. 1995) (570 points with 2 groups), Moons (scikit-learn developers 2007
(200 points with groups), Hypercube(200 points with 2 groups), Cluto (Karypis et al. 1999) (800 points with 8 groups), and Complex (800 points with groups). The last four datasets consist of disjoint and equal sized groups, so we can perform strictly fair k-means algorithms them. We place the detailed information of
these datasets in Appendix F Regarding the selection of a and 3, we set a; 3 = | and we also discuss more choices for a and B. and provide more experimental results, including the part of k-sparse Wasserstein Barycenter, in the Section F of the appendix. We use k-means++ (Arthur & Vassilvitskii 2007) as the k-means solver in our Algorithm
Results on (a, F)-F k-means. We compared the cost of (a, 3) -air k-means of our Algorithm ] and baselines. We choose the algorithm proposed by Bera et al. (2019) (denoted by NIPS19) and Böhm et al. (02TT) (denoted by ORL21) as the baseline. The construction of an e-approximate centroid set a theoretical algorithm that can be replaced by some efficient methods in practice. In our experiments, we adopted the alternative implementation by ManKuno et al. (2002). which combines the kd-tree (Friedman et al. 1977) and a sampling technique. Figure ssows that our algorithm gives the lowest cost of (a, fair k-means, indicating that Algorithm | 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.
Tiot
x10
Bank
x10
Adult
x10 Creditcard
X10
Census
Cost
1.6-
1.4
124
15
10
15
10
15
20
10
15
20
10
15
20
k
k
Moons
X10
Breastcancer
x10º
Cluto
x10'
Complex
1.5*
160
2.50
1.4-
Cost
2.25
1.3-
120-
3.5
100
1.75
15
70
1
10
15
k
k
k
Figure 1: The cost obtained by the algorithms with different At
CONCLUSION
In this paper, we utilize the insight on the relationship between the fair k-means problem and classic geometric structure, c-approximate centroid set, for developing novel "Relax and Merge" framework. can achieve a (1 + 4p + O(e)) 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 possible to extend our 'Relax and Merge" framework other types of clustering problems, such as the proportionally fair clustering (Chen et al. (201)) and socially fair k-means clustering (Ghadiri et al. 2021)
10

---

Published as a conference paper at ICLR 2025
6 ACKNOWLEDGEMENT
The research of this work was supported in part by the National Key Research and Develop- ment Program of China (NO.2021 20A 1000900) the National Natural Science Foundation of China INO.6227243,, NO.62432016) and the Natural Science Foundation of Anhui Province (NO.2200885MF163) We want to thank the anonymous reviewers for their helpful comments. We are grateful to Prof. Lingxiao Huang in Nanjing University and Qingyuan Yang for inspiring discussions.
REFERENCES
Mohsen Abbasi, Aditya Bhaskara, and Suresh Venkatasubramaniin.. Fair clustering via equitable group representations. In Proceedings of the 2021 ACM conference on fairness, accountability. and transparency, pp. 504-514, 2021.
Martial Agueh and Guillaume Carlier. Barycenters in the wasserstein space. SIAM Journal Mathematical Analysis, 43(():904 2011.
Salem Alelyani, Jiliang Tang, and Huan Liu. Feature selection for clustering: A review. Data Clustering, pp. 29-60, 2018.
Jason M Altschuler and Enric Boix-Adsera. Wasserstein barycenters can be computed in polynomial time fixed dimension. Journal of Machine Learning Research, 22(44):1-19, 2021.
Ethan Anderes, Steffen Borgwardt, and Jacob Miller. Discrete wasserstein barycenters: Optimal transport for discrete data. Mathematical Methods of Operations Research, 84:389 4099 2016.
David Arthur and Sergei Vassilvitskii. k-means++: the advantages of careful seeding. In Proceedings of the eighteenth annual ACM-SIAN SIAM symposium on Discrete algorithms, New Orleans, Louisiana, 2007. pp. 1027-1035. Society for Industrial and Applied Mathematics, 2007.
Julio Backhoff- Veraguus, Joaquin Fontbona, Gonzalo Rios, and Felipe Tobar. Bayesian learning with wasserstein barycenters. ESAIM: Probability and Statistics, 26:436-472, 2022.
Sayan Bandyapadhyay, Fedor V. Fomin, and Kirill Simonov. On coresets for fair clustering in metric and euclidean spaces and their applications. J. Comput. Syst. Sci., 142: 142:10, 2024.
Barry Becker and Ronny Kohavi. Adult. UCI Machine Learning Repository, 1996. DOI: http:///bb..r///222422////X3
(CC BY 4.0) license.
Suman Bera, Deeparnab Chakrabarty, Nicolas Flores, and Maryam Negahbani. Fair algorithms for clustering. Advances in Neural Information Processing Systems, 32, 2019.
Ioana Bercea, Martin GroB, Samir Khuller, Aounon Kumar, Clemens Rösner, Daniel Schmidt, and Melanie Schmidt. On the cost of essentially fair clusterings. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2019.
Anup Bhattacharya, Ragesh Jaiswal, and Amit Kumar. Faster algorithms for the constrained k-means problem. Theory of computing systems, 62:93-115, 2018.
Matteo Böhm, Adriano Fazzone, Stefano Leonardi, Cristina Menghini, and Chris Schwiegelshohn. Algorithms for fair k-clustering with multiple protected attributes. Operations Research Letters, 49(5):787-789, 2021.
Nicolas Bonneel, Julien Rabin, Gabriel Peyré, and Hanspeter Pfister. Sliced and radon wasserstein barycenters of measures. Journal of Mathematical Imaging and Vision, 51:22-45, 2015.
Steffen Borgwardt and Stephan Patterson. On the computational complexity of finding sparse wasserstein barycenter. Journal of Combinatorial Optimization, 41(3))736-761,2221 2021.
Vladimir Braverman, Vincent Cohen-Addad, H-C Shaofeng Jiang, Robert Krauthgamer, Chris Schwiegelshohn, Mads Bech Toftrup, and Xuan Wu. The power of uniform sampling for coresets. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 462-473. IEEE, 2022.
11

---

Published as a conference paper at ICLR 2025
Jianlong Chang, Lingfeng Wang, Gaofeng Meng, Shiming Xiang, and Chunhong Pan. Deep adaptive image clustering. In Proceedings of the IEEE international conference on computer vision, pp. 5879-5887, 2017.
Xingyu Chen, Brandon Fain, Liang Lyu, and Kamesh Munagala. Proportionally fair clustering. In International Conference on Machine Learning, pp. 1032-1041. PMLR, 2019.
Flavio Chicrichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii. Fair clustering through fairlets. Advances in neural information processing systems, 30, 2017.
Eden Chlamtáë, Yury Makarychev, and Ali Vakilian. Approximating fair clustering with cascaded norm objectives. In Proceedings of the 2022 annual ACM-SIAM symposium on discrete algorithms (SODA), pp. 2664-2683. SIAM, 2022.
Sebastian Claici, Edward Chien, and Justin Solomon. Stochastic wasserstein barycenters. In International Conference on Machine Learning, pp. 999-1008. PMLR, 2018.
Vincent Cohen-Addad, Philip N Klein, and Claire Mathicu. Local search yields approximation schemes for k-means and k-median in euclidean and minor-free metrics. SIAM Journal Computing, 48(2):644-66) 667, 2019.
Vincent Cohen Addad, Andreas Emil Feldmann, and David Saulpic. Near-linear time approximation schemes for clustering in doubling metrics. Journal of the ACM (JACM), 68(6):1-34, 2021.
Guy Barrett Coleman and Harry C Andrews. Image segmentation by clustering. Proceedings the IEEE, 67(5):773-785, 1979.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. MIT Press, Cambridge, MA, 3rd edition, 2009.
Marco Cuturi and Arnaud Doucet. Fast computation of wasserstein barycenters. In International conference on machine learning, pp. 685-693. PMLR, 2014.
Marco Cuturi and Gabriel Peyré. A smoothed dual approach for variational wasserstein problems. SIAM Journal on Imaging Sciences, 9(1):320-344 343, 2016.
Zhen Dai, Yury Makarychev, and Ali Vakilian. Fair representation clustering with several pro- tected classes. Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency, pp. 814 823, 2022.
Hu Ding and Jinhui Xu. A unified framework for clustering constrained data without locality property. In Proceedings of the Twenty-Sie Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '15, pp. 1471-1490, USA, 2015. Society for Industrial and Applied Mathematics.
Hu Ding and Jinhui Xu. A unified framework for clustering constrained data without locality property. Algorithmica, (2(4):808-852 2020.
Yefim Dinitz, Algorithm for solution of a problem maximum flow networks with power estimation. Soviet Math. Dokl., 11:1277-1280, 01 1970.
Petros Drineas, Alan M. Frieze, Ravi Kannan, Santosh S. Vempala, and V. Vinay, Clustering large graphs via the singular value decomposition. Mach. Learn., 56(1-3):9-33, 2004. doi: 10.1023/::MACH.000000 13..0093111.55916666 URL https://doi..rg/// wtt..///....................... 1023 MACH 00C0038113. 59016. 96.
Jack Edmonds and Richard M. Karp. Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM, 19(2):248 264, April 1972. ISSN 0004-5411, doi: 10. 1491324//21694 321699. URLLEttpss:/doii.rrrte
321699
Raphael A. Finkel and Jon Louis Bentley. Quad trees: A data structure for retrieval on composite keys. Acta Informatica, 4:1-9, 1974. doi: 10. 00.1007/BF00288933. URL htthtt:/p//doi org/ 10. 1100/1F002869000
L. R. Ford and D. R. Fulkerson. Maximal flow through a network. Canadian Journal of Mathematics, 8:399-409 1956. doi: 10.4153/CIM- 1041533CIM-1955-044-5 1956-04555.
12

---

Published as a conference paper at ICLR 2025
Jerome H Friedman, Jon Louis Bentley, and Raphael Ari Finkel. An algorithm for finding best matches in logarithmic expected time. ACM Transactions on Mathematical Software (TOMS), (3):209-226, 1977.
Zachary Friggstad, Mohsen Rezapour, and Mohammad R Salavatipour: Local search yields plas for k-means in doubling metrics. SIAM Journal on Computing, 48(2):455 -800, 2019.
Mehrdad Ghadiri, Samira Samadi, and Santosh Vempala. Socially fair k-means clustering. In Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, pp. 438-448 2021.
Elena L. Glassman, Rishabh Singh, and Robert C Miller. Feature engineering for clustering student solutions. In Proceedings of the first ACM conference on Learning @ scale conference, pp. 171-172, 2014.
Anupam Gupta, Robert Krauthgamer, and James Lee. Bounded geometries, fractals, and low- distortion embeddings. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings,, pp. 534-543. IEEE, 2003.
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2023. URL https:/ ///0: gurobi com
Lingxiao Huang, Shaofeng Jiang, and Nisheeth Vishnoi. Coresets for clustering with fairness constraints. Advances in neural information processing systems, 32, 2019.
Anil K. Jain. Data clustering: 50 years beyond k-means. Pattern Recognit. Lett., 31(8):651-666, 2010.
Ragesh Jaiswal, Amit Kumar, and Sandeep Sen. A simple 2-sampling based ptas for k-means and other clustering problems. Algorithmica, 70(1):22-46, 2014.
Tapas Kanungo, David M Mount, Nathan $ Netanyahu, Christine D Piatko, Ruth Silverman, and Angela Y Wu. A local search approximation algorithm for k-means clustering. In Proceedings of the eighteenth annual symposium on Computational geometry, pp. 10-18, 2002.
George Karypis, Hui-Hong Han, and Vipin Kumar. dynamic modeling. computer, 32(8):68-74) 75, 1999.
Chameleon: Hierarchical clustering using
Harold W Kuhn. The hungarian method for the assignment problem. Naval research logistics quarterly, 2(1-2):83-97, 1955.
Amit Kumar, Yogish Sabharwal, and Sandeep Sen. Linear-time approximation schemes for clustering problems any dimensions. ACM, 57(2):::1 2010.
Euiwoong Lee, Melanie Schmidt, and John Wright. Improved and simplified inapproximability for k-means. Information Processing Letters, 120:40 43, 2017.
Tianyi Lin, Nhat Ho, Xi Chen, Marco Cuturi, and Michael Jordan. Fixed-support wasserstein barycen- ters: Computational hardness and fast algorithm. Advances in neural information processing systems, 33:5368-5388 2020.
Meena Mahajan, Prajakta Nimbhorkar, and Kasturi R. Varadarajan. The planar k-means problem is np-hard. Theor. Comput. Sci., 442:13-21, 2012. doi: 00.10160.TC3.2010055..444 URL 2010. 05.03..55.3.
Yury Makarychev and Ali Vakilian. Approximation algorithms for socially fair clustering, In Conference on Learning Theory, pp. 3246-3264. PMLR, 2021.
Kamel Mansouri, Tine Ringsted, Davide Ballabio, Roberto Todeschini, and Viviana Consonni.
Quantitative trructre-activiny relationship models for ready biodegradability of chemicals. Journal of chemical information and modeling, 53(4):867887, 2013.
Jif Matoušek. On approximate geometric k-clustering, Discrete & Computational Geometry, 24(1): 61-84, 2000.
13

---

Published as a conference paper at ICLR 2025
Alberto Maria Metelli, Amarildo Likmeta, and Marcello Restelli. Propagating uncertainty in re- inforcement learning via wasserstein barycenters. Advances in Neural Information Processing Systems, 32, 2019.
Evi Micha and Nisarg Shah. Proportionally fair clustering revisited. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Schloss Dagstuhl-Leibnnzzzeeetru für Informatik. 2020.
Sérgio Moro, Paulo Cortez, and Paulo Rita. data-driven approach to predict the success of bank telemarketing. Decision Support Systems, 62:22-31, 2014.
Rehecca Nugent and Marina Meila. An overview of clustering applied to molecular biology. Statistical methods in molecular biology. pp. 369-404, 2010.
Julien Rabin, Gabriel Peyré, Julie Delon, and Mare Bernot. Wasserstein barycenter and its application to texture mixing. In Scale Space and Variational Methods in Computer Vision: Third International Conference, SSVM 2011, Ein-Gedi, Israel, May 29-Jume 2, 2011, Revised Selected Papers 3, pp. 435 446. Springer, 2012.
Tom Ronan, Zhijie Qi, and Kristen M Naegle. Avoiding common pitfalls when clustering biological data. Science signaling, 9(43))ree-rro, 2016.
Melanie Schmidt, Chris Schwiegelshohn, and Christian Sohler. Fair coresets and streaming algorithms for fair k-means. In Approximation and Online Algorithms: 17th International Workshop, WAOA 2019, Munich, Germany, September 12-13, 2019, Revised Selected Papers 17, pp. 232-251. Springer, 2020.
scikit-learn developers. scikit learn. http:://ellkiiiaaaaaa/////aaaa/p
gererated/sk learn learn. datasets. wakeaaaoksssssss moons htm Pasklearr .atasstss.....
make_moons 2007-2023.
Cédric Villani. Topics in optimal transportation, volume 58. American Mathematical Soc., 2021.
Wolberg.William, William, Mangasarian, Olvi, Strket, and Street, W. Breast Cancer Wisconsin (Diagnos- tic). UCI Machine Learning Repository, 1995. DOI: https://oo.oog//122443///CDV
Di Wu, Qilong Feng, and Jianxin Wang. Approximation algorithms for fair k-median problem without fairness violation. Theoretical Computer Science, 985:114332, 2024. ISSN 0304-3975. doi: Brieene//stticeee///////33333333
2023 URL httpsttts:// http://wwwwcccrre. wtt.:./ccenneeiret.t.t..... com/
Qingyuan Yang and Hu Ding. Approximate algorithms for k-sparse wasserstein barycenter with outliers. Proceedings of the Thirty-Third International Joint Conference Artificial Intelligence, IJCAI-24, pp. 5316-5325, 2024. doi: (0.24963/ijcai.2024588. URL URLthttss://doo 10. 70.24993/iicaan 2et.aa..022/5550 Main Track.
I-Cheng Yeh and Che-hui Lien. The comparisons of data mining techniques for the predictive accuracy of probability of default of credit card clients. Expert systems with applications, 36(2):
2009.
Zhe Yuan, Zhewei Wei, Fangrui Lv, and Ji-Rong Wen. Index-free triangle-based graph local clustering. Frontiers of Computer Science, 1803):183044, 2023. ISSN 2095-2236. doi: 10.1007/ sl 111704-023-2768-7
Jing Zhang, Ruidong Fan, Hong Tao, Jiacheng Jiang, and Chenping Hou. Constrained clustering with weak label prior. Frontiers of Computer Science, 18. 12 2023. doi: 10.1007/5117044-22-3333
Zhi-Hua Zhou and Zhao- Qian Chen. Hybrid decision tree. Knowledge-based systems, 15(8):515-525 2002.
14

---

Published as a conference paper at ICLR 2025
A C-APPROXIMATE CENTROID SET
The algorithm of constructing an e-approximate centroid set is proposed by Matoušek] (2000). Here briefly introduce the idea. First, we use quadtree to partition the space into hierarchical cubes. At each level of the tree, we construct grid. The length of the grid is set to ensure that the grid points can always cover all approximate centroids of all cubes this level. The approximate centroid set is the union of all grid points across all levels.
In Figure 2 we visually illustrate the difference between the k-means clustering center and the fair k-means clustering center. The vanilla k-means induces Voronoi diagram, so that every k-means center is located the centroid of k-means cluster. However, fair k-means center can be located at the centroid of any potential cluster that satisfies the fairness constraints. The e-approximate centroid set structure can help us to find these potential centroids and preserves the fairness constraints for later procedures.
(b)
Figure 2: 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.
B OMITTED PROOFS
Theorem 2 If T' is an e-approximate centroid set of U P(0, Algorithm Preiittmmmrrttumsss (1+4p+0(e)) approximate solution for k-sparse Wasserstein Barycenter problem.
To prove this theorem, need the following lemma.
Lemma 6. IfT an c-approximate centroid set of UR p(o , solving LP then T is a (1 + O(c)) O(c))=approxxmaat Wasserstein Barycenter.
and w(t) for each t obtained by
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 al.) 2016) (Section 2, Equation 4). Therefore, if we calculate e-approximate centroid set T. then T can always cover the locations T i.e., Cost T, oi.) S (1 + C(e))(ost(P,)) T"x oi. S (1 + ((+)) obtain the conclusion of Lemma
So using the same proof idea with Lemma
Combine Lemma and Lemma I we arrive at Theorem
C THE ROUNDING TECHNIQUE
Our rounding algorithm consists of three steps: constructing network structure of Minimum Cost Circulation Problem (MCCP), setting the parameters of each edge based on fractional solution obtained by Algorithm 1 and solving the MCCP above. This reduction to MCCP is inspired by
15

---

Published as a conference paper at ICLR 2025
Ding & Xu (2015) (Section 4.3), while having some fundamental differences with their method.
Our algorithm has different objectives compared to theirs, as it is based on 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 can be completed in (2) time even when using the vanilla Edmonds-Kan Karp algorithm (Dinitz 1970
Edmonds & Karp 1972).
The process of our algorithm is described follows. Recall that the dataset P consists of different groups, i.e., P - p(() and assume that the groups disjoint. By executing the Algorithm | we obtain a center set S and corresponding fractional assignment matrix 03.. Now, in order to build
minimum cost circulation instance, need to construct network structure Figure 3 and for each
arc (u, v). we should set the lower/upper bound of the flow [(u, v) and its cost c(u, v). We create a copy of S, denoted by 5(0, for each group p(), Each 51 is "hub" used for transit, specifically to receive weights from group p(t) and transmit them to S. To facilitate understanding, we can imagine that each 8) accepts the weights from group P(1) We set c(p)) ss i.e., the cost of the are from any Pj E P(()
(i) E 8()), where / [k], and its corresponding 51 S is in the same position, but only (6)
(i)
where j E [n,(0], to an 81 E (()) to be 110))) $1 The cost of the remaining arcs are
p())
50
[0.1]
[1.1]
(w(s))((())))
Source
Sink
p(m)
[0.1]
[Iw(s))
(s)]]
[n.n]]
Figure 3: The instance of the minimum cost circulation problem established through (S, 03). The upper and lower bounds of the flow for each arc are annotated in the graph.
Next, we set the lower bound and the upper bound of the flow on each arc, as shown in Figure First, the flow from the "Source" node to each p E P is restricted to 1, which means that each point p E P(1) has weight of 1 assign to S(1), Then, between each p(() and its "hub" ((+), the flow from each Pj E p() to each s14) E S(() is bounded by [o, 1]. Here, the flow I'(2,
(i) , 8 (0)) denotes the amount of
the weight that assigned from pi to 81 E S in an (a, 3a)r k-means solution. Subsequently, recall that in the solution (S, Φz) we obtained before, the weight received by a center E S from group p(t is (s))..). We bound the flow {() st) by (s)). [w(() Finally, the flow from each 81 to the "Sink" node bounded by [w(ss)], (=))]]], and we set fSinnk Source) = n to form circulation. At this point, we have established an instance of the minimum cost circulation problem, denoted by MCCP(S, o'y). Obviously, we have the following observation:
(6)
Observation 1. d'g induces a feasible solution of MCCP(S, Φ5..
The observation straightforward because the flow induced by d5 meet all the bounds applied to the flow. Then, we give the proof of Lemma mentioned in Section 3.1
16

---

Published as a conference paper at ICLR 2025
Lemma 4
There exists algorithm that round fractional solution of (a: B)- k-means to integral with at most 2-violation while the cost does not increase.
Proof. is known that the minimum cost circulation problem has an integrality property (Cormen et al. 2009), which guarantees that if the ares have integer capacities, there will always be optimal solution with integer flow values on each arc. Utilizing an algorithm for minimum cost circulation problem minimum cost flow problem (the two problems equivalent), which converges to integer solution like Ford-Fulkerson (Ford Fulkerson, 1956). we can obtain an integer optimal solution of MCCP(S, (gg), which has cost larger than the solution induced by d3-
Next, we prove that the assignment matrix, say d'g. induced by the integer optimal solution of MCCP (g)) is 2-violation assignment from P to S. Recall that we presented the definition of the violation factor in Section 2 An assignment matrix Øs is a X-violation solution if 3, LpEp Φs 8) < Pcs P() (p, 8) a Epep (s 8) + X, Vs E S, Vi E [m). According to the construction
procedure of MCCP(S, o3), the lower bound of the flow f(s si) is (wo (st)), which satisfies:
(s:) 2 ([w(s() 1)1
Los[((s)) - [3j
(13)
[az [w][w[ - Oii -1
[w][) - ox) -
Note that the upper bound of the flow f(1,, Sink) is [w((s)] so have:
[ (6) (st)
2 0: [s))] - 0gi
(14)
2 a (st) 2,
and similarly,
(w( (s:) S 3, [ (ss))
[1) $ 3 (s)) +
33 +
(15)
which indicates that 0's is a 2-violation assignment and complete the proof of Lemma
D FIXED SUPPORT WASSERSTEIN BARYCENTER
Given discrete distributions (weighted point sets, each set has total weight sum to 1)
p()).... p(m) and a set I' of WB, the objective of fixed support WB as follows:
m (9 (0
min
T,11
s.t.
Σ
1,
WE [m] Vi (n]
Σ Dif wo (P(w)) = Mjj v W Vj [[T]]
(16)
12
Σ yj = 1,
j=l
(1) 0,
Vl e (n Vj E [T]]
yソ 0, Vje e [[]]
It is easy that fixed support WB problem be solved using linear programming method.
Several existing works on solving LP (16) include (Claici et al. 2018 Cuturi Doucet 2014; Cuturi
& Peyré 2016 Lin et al. 2020
17

---

Published as a conference paper at ICLR 2025
For the sake of completeness, we need to clarify how the solution to the k-sparse Wasserstein barycenter solution is guaranteed to be a distribution. After we run Algorithm 1, we obtain the support S (the locations of centers) of the returned solution and the assignment matrix & (the (0
transportation weight from = P! to f Sj is denoted by (p, f) = Tig in (16). The key question is how ensure that the summation of the weight of points in S is equat 1. Let us consider an arbitrary given distribution (or "group" in the context of fair k-means), e.g., p(), For every facility f in S, we define its weight w(f) = 2pppar (p. This ensures that the total weight of must be equal the total weight of p(t), which is because p(t) is distribution. The special fractional
choice of p() can be arbitrary because, recall that k-sparse WB can be version of strictly fair k-means, meaning no matter which given distribution you choose, you will obtain the same weight distribution of S. The optimization will not change by setting the weight of S because the weight of S does not affect the cost.
E EXTEND ALGORITHM TO k-MEDIAN AND M-MEAS IN GENERAL METRIC SPACE
Although we mainly consider the fair k-means problem in Euclidean space in this paper, for the sake of completeness, this section, we illustrate how to extend our framework to solve k-median and k-means in general metric space. In summary, if the potential facility set is given, our framework achieves a (1 + - -pprrxximttee solution for k-median ((2 + -aparoxxxeee solution for k-means) in metric space, where is the approximation ratio for vanilla i--median (k-means) with a constant violation factor. If the metric space has a fixed doubling dimension (Gupta et al. 2003), then equipped with existing PTAS for metric k-median and k-means (Cohen-Addad et al. [021] 2019 Friggstad
et al. 2019). the best approximation ratios our framework can achieve are (3+ O()) for fair k-median and 10 O(e) for fair k-means.
Unfortunately, our theoretical guarantees in general metric space are weaker than those of Bera et al. (2019). which they obtained (p 2) approximation for k-median and (vp+ 2)2+2)22aa a)2-approx for k-means. The obstacle to achieving better approximation ratio for our framework is the "candidate set".. In Fuclidean space, we have an approximate centroid set. However, in general metric space, how can we obtain candidate set that has similar properties to Proposition[] which provides a more powerful tool than the basic triangle inequality? This not only a potential future work of framework but also important open thcoretical problem.
k-Median in metric space. Firstly, we consider fair k- k-median in general metic space. We use dist(.,)) to denote the distance between two points. We assume that the potential facility set T is given. Therefore, in Algorithm | we just use the given facility set rather than computing the approximate centroid set. The cost of fair k-median can be written as
Cost = ΣΣ {i)sst(p,)))55 (p))(
(17)
pEP SES
Similar to Lemma we have the following lemma.
Lemma 7. Let be any positive number. If we suppose Cost(P,T.o7)) < n- OPT, then the
solution (S, ob)) returned by Algorithm (the construction Tf should be slightly changed) is an
(1 - (7 + 1)p) approximate solution for fair k-median problem metric space, where p is the approximation ratio of vanilla k-median.
Proof. Now consider another assignment strategy: firstly assign P to T according o ( recall that of is the optimal fractional assignment matrix from P to 7), and then we assign every weighted point in T to some S such that is closest point to л (t). Since di is the optimal
18

---

Published as a conference paper at ICLR 2025
assignment matrix from P S, the cost of this assignment strategy should have:
Cost(P,S,053 -
Σ E
dist(p.N((,,)))f((11
PEPIET
dist(ppt) + d(st(t, 07(0.
NET PEP
(18)
ΣΣ
dist p. (p,t) +
((st
PEP
PEP
(h)
The second inequality is triangle inequality. Then we bound (a) and (b) separately, Firstly,
(a) ΣΣ
dist(p, (p.) Cost Φ7) n OPT
(19)
PEPЛET
Next, we focus on (b). Suppose Smedion the optimal k-median solution T. Then we have:
(b) ΣΣ
dist (L(.
PEP TET
Σ
(istttt Smedion (pp
P
PEPIET
(20)
ΣΣ
dist(I,Nil,, S Smedian 1)0's (v, 8) (T(
pEP KET
SES.pt
Σ dist(t, 8) 8) (p, (p,
p
PEPIET
&ESupt
Further, according to the triangle inequality, have
S
ΣΣ
Σ
[dist(l,p) + dist(p, "3 (1, (1,)))
PEP 1ET
SESape
p
dist(t, p)ot (p,
pEP &ESopt
(21)
Σ dist 8)0 (),
PEP TET SES.ut
p Σ dist(t,p)ot +
Σ dist(p, 5)05 (p. 8).
IET
PE SE
The last equality holds because for any p E P. P.E.ES. The first term is exactly p times of (a) and the second term equals p. P-OPT. Through combining (a) and (b), we can obtain approximation factor of 1) (1 1)p.
Eses.... 0
Sopt (p, and Eier Φ (p.
k-Means in metric space. Using the same idea of Lemma 7 with squared triangle inequality dist? (a, b) < 2dist"((acc) + (c, (c, b), we can immediately obtain the following corollary.
Corollary 1. Let 1j be any positive number. If we suppose Cost(P,T, ΦT) S 1 OPT, then the solution (S, Φ3) returned by Algorithm / (slightly changed as above) is (2n + (4n 4) approximate solution for fair k-means problem in metric space, where p the approximation ratio of vanilla k-means.
When considering k-clustering problem in metric space, usually assume that the potential facility set is given. We just use it as our candidate set Hence, the 17 = in the above analysis, which leads (2 + pppopoooonnnooon for fair k-median and (2 + apprromaxiinaoo for fair k-means.
19

---

Published as a conference paper at ICLR 2025
F SUPPLEMENTARY EXPERIMENT
F.1 DATASETS
The detailed information of our datasets is shown T The group partition of every dataset is based the "Group Column". Every group column has some group values. The set of groups the Cartesian product group values of all group column. For example, the groups Bank dataset (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.
Dataset
Size
Dimension
Group Column
Groups Values
Bank
9999
3
marital
married, single, divorced yes, no female, male Amer-ind, usian-pac-iss
default
Adult
4522
5
sex
race
black, other, white married, single, other, null
Creditcard 30000
5
marriage
education
7 groups
Census1990
50000
12
dAge
8 groups
iSex
female, male
Moons
200
2
color
2 groups
Hypereube
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
Table 2: Detailed Datasets Information
F.2 COMPARISON ON COST OF STRICTLY FAIR k-MEANS
We compare our strictly fair k-means algorithm with the ffte--oftheee algorithm ORL21 (Böhm et al. 202I). Both ORL21 and Algorithm can return integral solution with no violation. Figure shows that our method has significant advantage terms of the clustering cost.
Moons
Hypercube
x10
Cluto
x10 Complex
200
ORL21
1200
1.5
Ours
Cost
180
1000
4.0
3.8
160
800
3.6
3.4
10
15
20
10
15
20
10
15
20
10
15
20
k
k
Figure 4: The cost of strictly fair k-means.
F.3 COMPARISON COST WITH DIFFERENT & AND (a,
p(5)
In the main paper, we set a; 3, [P] Here, we try different a and 3 to compare our algorithm
to baselines. In order to make sure that the values of a and 3 are feasible, we introduce the parameter 8 E (0, 1), which represents the degree of relaxation of faimess constraints, with larger 8 indicating
[(0]
||(a| (1 8). We set = 0.1 and 0.2 to -P
looser constraints. We set a; TP I and B,
compare the cost with baselines. The results shown in Figure and Figure respectively.
20

---

Published as a conference paper at ICLR 2025
In fact, 5 increases, the fairness constraints of the (a, 3)-r k-means problem become more relaxed, and the corresponding fair k-means problem approaches the vanilla k-means problem. In cases where 8 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.) 2002]) it is mentioned that when ò = 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 value.
X100
Bank
x10
Adult
x10 Creditcard
x10
Census
16-
16-
5.25
Cost
5.00
4,50
4.25
10
15
10
15
10
k
Moons
X10
Breastcancer
x10
Cluto
x10²
Complex
2.4
1.4
Cost
140
2.2
1.3
4.0-
120
2.0
1.2
3.5
1.8
1.1
10
k
k
Figure Comparison on Clustering Cost with 0.1
NIS19
ORL21
X10
Bank
x10
Adult
x10
Creditcard
x10
Census
13-
16
5.25
14-
Cost
10-
13*
12
4.75
4-
10
4.50
9-
5-
2-
4.25
13
10
Moons
Breastcancer
x10
Cluto
Complex
4.00
2.0
Cost
1.3
3.75
120-
3.50
1.8
100-
1.1
3.25
1.7
10
15
15
k
k
Figure 6: Comparison on Clustering Cost with d = 0.2
F,4 COMPARISON ON COST OF S-SPARSE WASSERSTEIN BARYCENTER
We compare our algorithm with the very recent work Yang & Ding 2024) (denoted by IJCA124) who obtain (2 + approxxmaae solution of k-spaase WB. The results are shown in Figure 7 In most cases, our algorithm can achieve 10%-30% cost advantage over the previous work.
F.5 COST ON DIFFERENT SAMPLING RATTO
In our algorithm, the most time consuming step is to solve LP(2) on T. A key observation during experiment that, after solving I.P on T. large amount of points of T have weight of 0.
21

---

Published as a conference paper at ICLR 2025
Moons
x12
10
Cluto
X20
Complex
4.8
133
[CAD4
4.8
Cost
1.1
1.-
60-
1.0
1.5
4.0
3.-
50
0.5
Figure 7: Comparison on the Cost k-sparse Wasserstein Barycenter
Therefore, it is possible to reduce the size of I'' while maintain the quality of T. Mcanwhile, smaller helps 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|] [ with different k. The results are shown in Figure C In these figures, we can see that in most cases, the cost of sampled 7 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).
Bank
Adult
1e13
Creditcard
1.5
4-
2-
2-
0.5
300%
50%
20%
10%
100%
50%
20%
10%
100%
50%
20%
10%
100%
50%
20%
10%
1c8
1.7
1000
75
1.5
1.00
1.0
0.50
25
0.25
100%
10%
50%
20%
10%
100%
20%
10%
100%
50%
10%
Figure 8: The cost centriod set T with different sampling ratio when k 5
1e13
1c0
0.75
1.5
0.50
2-
0.5
100%
50%
20%
1056
100%
100%
50%
20%
10%
100%
50%
10%
140
1.65
Complex
100
3
75
1.0
Cost
2-
50
0.5
50%
20%
1056
100%
100%
30%
20%
10%
100%
50%
20%
10%
Figure 9; The cost centriod set T with different sampling ratio when h: 10
F.6 RUNNING TIME WITH DIFFERENT SAMPLING RATIO ON T
As we discussed in sampling on relaxed solution T can reduce the running time while the overall cost not increasing much. We also test the rumning time with different sampling ratio. In summary, the running time of solving LP(2) on T and overall Algorithm I shown in Table 3 and Table can be significantly reduced by sampling.
22

---

Published as a conference paper at ICLR 2025
Bank
Adult
1d13
Credibcard
166
Census
3
4-
1.0
0.5
0
0.0
300%
50%
20%
10%
100%
50%
20%
10%
100%
50%
20%
10%
100%
50%
20%
10%
Moons
168
Breastcancer
Cluto
Complex
1.00
1.5
1.00
3.
75
0.75
2-
50
25
14
0.0
0.00
0-
200%
50%
20%
10%
100%
50%
20%
10%
100%
50%
20%
10%
100%
50%
20%
109
Figure 10: The cost on centriod set 7 with different sampling ratio when k
15
Bank
Adult
Creditcard
Census
1.00
0.75
0.50
2-
0.25
0.5
0.00
0.00
0.0
100%
50%
20%
10%
100%
50%
20%
10%
100%
50%
20%
10%
100%
500
20%
10%
Moons
Breastcancer
Cluto
Complex
1.0
Cost
2-
0.5
25
0-
0.0
0.0
0-
100%
50%
20%
10%
100%
50%
70%
10%
100%
50%
20%
10%
100%.
50%
70%
10%
Figure 11: The cost on centriod set with different sampling ratio when & = 20
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 Time (seconds) of solving LP(2
on with different sampling ratio
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
Table 4: Overall time (seconds) with different sampling ratio when 20
23

---

Published as a conference paper at ICLR 2025
F.7 COMPARISON OF RUNNING TIME WITH BASELINES
We compared the running time our algorithm (Algorithm with our rounding technique) with the baseline NIPS19 9 (Bera et al. 2019). For strictly fair datasets, we also tested the running time of Algorithm and ORL21 (Böhm et al. 2021). The results are shown Table and Table Below, we provide detailed analysis the comparisons.
Comparison between Algorithm 1 and NIPS19 (Bera et al. 2019). Algorithm ! and NIPS19 both have two important subprocedures: linear programming and the k-means algorithm. These two steps are the bottlenecks for Algorithm|] T and NIPS19. Specifically, NIPS19 first runs the k-means algorithm (i.e., k-means++), and then calls the LP solver once to compute the fractional assignment. A different part of our Algorithm| i that it calls the LP solver twice, once to compute the weights of candidate set 7 and once compute the fractional assignment, and calls the k-means algorithm once. In Algorithm!] [ we only need to run k-maans on T' which should be much smaller than the whole dataset, leading However, the first call to the LP solver to compute the weight of 7 consumes more time than the second call because [T] usually. We illustrate the running time of every critical subprocedure of both algorithms in Table Our k-means step is faster, but we have the running time comparison between these two algorithms is complex. Generally speaking, LP takes more time than k-means, which means our Algorithm| Ussually runs slower than NIPS19. However, with the development of LP solvers, we can expect that the runtime Algorithm could further reduced with more advanced LP solvers.
less running time for the k-means subprocedure compared NIPS19.
an extra LP step. Therefore,
Construct T
LP on
k-means
LP on
Rounding
Total
Algorithm
0.01
2.4
<0.01
1.23
<0.01
3.78
Bank
NIPS19
/
0.14
0.81
<0.01
1.11
Algorithm
0.01
4.06
<0.01
2.27
<0.01
6.51
Creditcard
NIPS19
/
0.18
2.05
<0.01
2.39
Al Algorithm
0.01
7,51
0.02
5.19
<0.01
12.99
Census1999
NIPS19
/
0.30
3.94
<0.01
4.42
Algorithm
0.01
4.14
<0.01
1,80
<0.01
6.12
Adult
NIPS19
0.18
1.23
<0.01
1.59
Al Algorithm NIPS19
0.01
0.19
<0.01
0.82
<0.01
1.33
Breastcancer
0.10
0.22
<0.01
0.45
Table 5: Running time (s) non-strictly fair datasets
Construct T
LP on T
k-means
LP S
Rounding
Total
Algorithm
0.01
0.18
<0.01
0.64
<0.01
0.83
19PS19
0.07
0.70
0.01 /
0.78
Moons
Al Algorithm
/
<0.01
0.59
ORL.21
0.02
0.48
Algorithm
0.01
1.01
<0.01
1.30
<0.01
2.36
NIPS19
0.07
1.54
<0.01 /
1.66
Cluto
Algorithm
/
0.01
0.56
ORL 21
0.56
0.72
Algorithm
0.01
1.08
<0.01
0.61
<0.01
1.71
N9PS19
/
0.05
0.72
<0.01 /
0.79
Complex
Algorithm
0.01
0.58
ORI.21
0.56
0.72
Algorithm
0.01 /
5.71
0.01
4.40
<0.01
10.27
19PS19
0.15
2.58
<0.01 /
2.87
Hypercube
Al Algorithm
< 0.01
0.39
ORI.21
0.67
/
0.83
Table 6: Running time (s) on strictly fair datasets
24

---

Published as a conference paper at ICLR 2025
Discussion on the construction of T. According Algorithm | T should be approximate centroid set (Matoušek] 2000). Thanks to the open-source project by (Kanungo et al. 2002), which provides efficient implementation of the approximate centroid set, used their algorithm as part of our procedure in our code. Kanungo et al. (2002) used a sampling technique, leading to a trade-off between performance and efficiency. In our experiment, we sampled 10% of points in the approximate centroid set as T. A higher sample rate yields better performance (lower cost) but longer running time.
Besides, an implicit benefit of the construction of 7' is that it is irrelevant to the parameters k, a, and So we consider a real scenario that we need to repeatedly try different choices for these parameters (e.g., we may want to tune the value & and select the most satisfying result), the step of constructing and performing linear programming on T can be seen as preprocessing of datasets before the tuning. Namely, we just need to run this preprocessing one time, and consequently the amortized cost over the whole tuning procedure can reduced significantly.
Running time comparison strictly fair datasets. For strictly fair datasets, consider Algo- rithm 1 NIPS19, Algorithm 2, and ORI.21 Algorithm has an advantage efficiency in most datasets. The primary reason that Algorithm 20nimmm@nnnn only calls the k-means algorithm need to solve the LP. As for ORL21, it needs to run k-means for each group and then choose the best one. As result, ORL21 takes longer time than Algorithm especially on the datasets with large number of groups
and does not
F.8 EXPERIMENTS OF OUR ROUNDING ALGORITHM
In this section, we implement our rounding algorithm in Appendix and compute the violation factor across different datasets and parameters. For convenience, we parameterize a; and 3, for the i-th
group using a single parameter 5. Specifically, we set 3 -1(0)((18) and a P 8) Generally
p(o)
speaking, the smaller the 8, the stricter the fairness constrains In Table 8 introduced by our rounding algorithm is less than in most of the cases and never exceeds which aligns with theoretical analysis.
9
the violation
dataset
k=2
4
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
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 7: Violation factor of our rounding algorithm with different A: (6 0)
dataset
k=2
8
10
12
14
16
18
20
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 8: Violation factor of rounding algorithm with different ls (6 0.1)
25

---

Published as a conference paper at ICLR 2025
dataset
k=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.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.50
0.56
0.39
0.51
0.69
0.19
0.57
0.56
0.64
0.75
0.65
Breastcancer
0.26
0.42
0.26
0.69
0.39
0.29
0.67
0.80
0.81
0.85
0.68
Table 9: Violation factor of our rounding algorithm with different l: (6 = 0.2)
26


Reviews:
[{"review_id": "YKKQGM2W0n", "reviewer": "Reviewer_9f2Z", "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.", "questions": "1) Is it possible to obtain fair $k$- clustering without any fairness violation without the requirement of equally sized groups? \n\n2) 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.\n\n3) Can you clarify how the solution to the k-sparse Wasserstein barycenter solution is guaranteed to be a distribution? Is the optimization slightly changed?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 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. \n\n2) 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.\n\n3) 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.\n\n4) 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.", "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. \n\n2) 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "krCWwiXePg", "reviewer": "Reviewer_GbWs", "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.", "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？\n\nQ2: 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? \n\nQ3: 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?\n\nQ4: 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?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The strength of this paper can be summarized as follows.\n\n1. 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.\n\n2. 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.\n\n3. This paper is well-written and the proofs are easy to follow. \n\n4. The empirical evaluations demonstrate that the proposed framework achieves much better performances on clustering quality compared to the previous works.", "weaknesses": "The weakness of this paper can be summarized as follows.\n\n1. 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. \n\n2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CPorN7B8mF", "reviewer": "Reviewer_9LbE", "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$.\n\nThe 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.\n\nTechnically, 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.\n\nOverall, I think this paper reaches the acceptance bar.", "questions": "1. Can one extend the results to the fair $k$-median?", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Improved approximation algorithms for an important problem.\n2. The idea is simple but very useful.\n3. Experiments show it is also promising for practice.", "weaknesses": "1. The running time of the first algorithm is exponential on $d$. Thus the result does not scale in high dimensions.\n2. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "IvNMjlwkdA", "reviewer": "Reviewer_MEJb", "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]).\n\n[A] https://theory.stanford.edu/~nmishra/Papers/clusteringDataStreamsTheoryPractice.pdf\n\nAdditional 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.", "questions": "Some questions can be found in the other part of review.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Fair clustering is a relevant problem, and the paper gives an approximation algorithm better than the known results in the Euclidean setting.", "weaknesses": "- The centroid set-based algorithm is specific to the Euclidean setting and cannot be extended to general metric spaces.\n- The exponential dependence of the running time on d may be problematic for high-dimensional data.\n- The techniques have mainly been borrowed from previous works. So, the theoretical contribution has limited novelty. \n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)