Better Algorithms for Individually Fair $k$-Clustering
Authors: Maryam Negahbani
Deeparnab Chakrabarty
Venue: NeurIPS 2021 Poster (2021)
Keywords: Clustering
Fairness
Approximation
Unsupervised-Learning

Abstract: We study data clustering problems with $\ell_p$-norm objectives (e.g. \textsc{$k$-Median} and \textsc{$k$-Means}) in the context of individual fairness. The dataset consists of $n$ points, and we want to find $k$ centers such that (a) the objective is minimized, while (b) respecting the individual fairness constraint that every point $v$ has a center within a distance at most $r(v)$, where $r(v)$ is $v$'s distance to its $(n/k)$th nearest point. Jung, Kannan, and Lutz [FORC 2020] introduced this concept and designed a clustering algorithm with provable (approximate) fairness and objective guarantees for the $\ell_\infty$ or \textsc{$k$-Center} objective.  Mahabadi and Vakilian [ICML 2020] revisited this problem to give a local-search algorithm for all $\ell_p$-norms. Empirically, their algorithms outperform Jung et. al.'s by a large margin in terms of cost (for \textsc{$k$-Median} and \textsc{$k$-Means}), but they incur a reasonable loss in fairness. 
In this paper, our main contribution is to use Linear Programming (LP) techniques to obtain better algorithms for this problem, both in theory and in practice. We prove that by modifying known LP rounding techniques, one gets a worst-case guarantee on the objective which is much better than in MV20, and empirically, this objective is extremely close to the optimal.  Furthermore, our theoretical fairness guarantees are comparable with MV20 in theory, and empirically, we obtain noticeably fairer solutions.
Although solving the LP {\em exactly} might be prohibitive, we demonstrate that in practice, a simple sparsification technique drastically improves the run-time of our algorithm.

Better Algorithms for Individually Fair k: K-Clustering
Deeparnab Chakrabarty' Department of Computer Science Dartmouth College Hanover, NH 03755
Maryam Negahbani
Department Computer Science
Dartmouth College Hanover, NH 03755
deepcθcs. dartmouth. edu
maryan@cs dartmouth. edu
Abstract
We study data clustering problems with fn-ormm objectives (e.g. k-MEDIAN and k-MEANS) the context of individual fairness. The dataset consists points, and we want to find & centers such that (a) the objective is minimized, while (b) respecting the individual fairness constraint that every point v has a center within distance most r(e), where r(v) is v's distance its (n (n/k)th nearest point. Jung, Kannan, and Lutz [FORC 2020] introduced this concept and designed a clustering algorithm with provable (approximate) faimess and objective guarantees for the fo or k-CENTER objective. Mahabadi and Vakilian [ICML 2020] revisited this problem give local-search algorithm for all f,-nomss. Empirically, their algorithms outperform Jung et. al.'s by large margin in terms of cost (for k- MEDIAN and k-MEANS), but they incur reasonable loss in fairness. In this paper, our main contribution is to use Linear Programming (LP) techniques to obtain better algorithms for this problem, both in theory and in practice. We prove that by modifying known LP rounding techniques. one gets worst-case guarantee on the objective which much better than in MV20, and empirically, this objective is extremely close to the optimal. Furthermore, our theoretical fairness guarantees are comparable with MV20 in theory, and empirically, we obtain noticeably fairer solutions. Although solving the LP exactly might be prohibitive, we demonstrate that in practice, a simple sparsification technique drastically improves the run-time of our algorithm.
Introduction
As machine learning algorithms are widely used in practice for making high-stakes decisions affecting human lives, there has been a huge body of work on FAIR-ML trying to ensure 'fairness' in the large intersecting bodies of work one body's
solutions returned by these algorithms. There main focus in to understand what 'fairness' means (e.g. [26 39 38 36 14 25)) in various different
contexts, and the second body's 's focus has been on addressing the algorithmmic challenges brought forth by these considerations (c.g., [24] 33 29 5)).
This paper falls in the second class. In particular, consider an individual fairness model proposed by Jung, Kannan, and Lutz 25 for a k-clustering problem. Given points (clients) in a space
with metric distance find & points (facilities) S C X, minimizing (EvEx d(u, SyP) 1/p where d(v, S) is e's distance the closest point in S. This includes k-CENTER, k-MEDIAN and the popular k-MEANS objective for 0o, = and p = 2 respectively, problems which have been extensively studied 22 23 27 4 [2] in the algorithms literature. Jung et. al. [25] proposed that in this context solution would be deemed individually fair, if for every client E X there is an open facility not too far from it. More precisely, if there is facility within distance r(v) which is the smallest radius
Supported by NSF grant #2041920
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

around u that contains n//k points. The rationale behind n/ is that if all the points had equal chance of getting picked as facility, each client would expect a facility to be open within distance r(v). Furthermore, this formulation encourages solution to open more facilities in dense areas of the metric which is motivated by the facility location application of clustering.
Jung et al. [25] gave a solution where every client u was served within a radius of 2r(v), which as a jargon called 2-approximate fair solution. However, their solution did not explicitly consider the "objective" function (k- MEANS/K-MEDDANN for instance) in the clustering problem, which is often used as a proxy to measure the quality of the clustering. This was addressed in a follow up paper by Mahabadi and Vakilian [29] who gave a (7, (pp)) aaproximiatin with respect to the 4 4--norm objective. That is, they give local-search based solution which is 7-approximately fair, but the objective is violated by some Cp-factor where the constant C is rather large (for p = 1, the factor is 84). The theoretical running time of their algorithm is Opk-"n*)
1.1 Our Contributions
The main contribution of our paper is to give improved algorithms for this problem using linear programming rounding. Our study stems from two observations: one, that the problem at the core of Jung et al. [25] was in fact studied as "weighted/priorty k-CENTER problem" by Plesník [32], and that if all the r(u)'s were the same (which may not at all be the case). then the clustering problem has also been studied under the guise of centridian/ordered median problem [3] 8 [1]. Combining ideas from these two bodies of work, we design an (8, 8) algorithm for the --MERAN problem. which obtains an 8-approximation for both cost and fairness (our cost guarantees improve as p grows).
Result 1. There is an (8, 21-2/p) 21-2//)aapproximaati algorithm for FATR- k) -LUUSTERRNG that runs in LP solving time plus Ö(n²), overall Ö(kn*). In particular, we have (8, 8) s)ppporoxnnttoon and (8, 4) a>aaproximatiion algorithms for FAIR-K-MEDIAN and FAIR-K-MEANS, respectively.
Remark. The approximation factor compares itself with the optimal solution which opens centers at the points in X. This is also the notion considered by [29 and [25). If the optimal solution allowed to open centers anywhere in the real space, then one has an additional factor 2 loss in
the approximation (15]. Whether this extra hit of factor 2 is necessary, we leave as an interesting algorithmic question.
Although solving an LP may seem prohibitive in practice, we can obtain a much faster running time by implementing sparsification routine (inspired by (2) with marginal hit in the fairness and clustering cost (see Lemma 5) for details). Empirically, this greatly decreases the running time, and is often faster than the [29] implementation.
In our experiments, we also find that our theoretical bounds are too pessimistic. Indeed, we show that our algorithm's 's cost is most %1 more than the optimal clustering cost (which does not have any fairness violation), almost always, and never more than %15 in the rest. Furthermore, our maximum fairness violation is at most factor of 1.27 which is much better than theoretical guarantec of 8. We also do a more fine-grained analysis of the fairness violation : consider a vector where each coordinate stands for clients "unfairess" indicating the ratio of its distance to r(v). When we plot this as a histogram, we find that most of the mass is shifted to the "left", that is, the percentage of clients who satisfy their fairness constraints is significantly larger than in the (29] solution. This seems to suggest the linear program, which is trying to minimize the cost, itself tries to increase the
number of fairly treated clients. We leave a theoretical investigation of this phenomenon for future work.
Our experiments also demonstrate the price of fairness. We find that our linear programs, which maintains absolute fairness, have objective value considcrably larger than that of (29]. On the other hand, if we tune the "fairness violation" of the linear program to match that of (29] then the objective value of our algorithm drops. We run experiments to further elaborate on the inherent cost of fairness in our datasets by demonstrating how the optimal cost changes with respect to varying degrees of fairness relaxation.
It is worth noting that our algorithm works for arbitrary values of rvv) > 0 for points v (and this may true for (9) as well), and we present our results thus. This setting might be of interest in applications where the "fair radius" may not be n/k /k but something more nuanced.

---

1.2 Other related work
k-CENTER has a 2-approximation due to Gonzales, and Hochbaum and Shmoys 17 21 and they prove it is NP-hard to get better approximations. k- k-MEDIAN, and k-MEANS are hard to approximate within factors better than 1.73 and 3.94 [9 respectively with current best approximations being 2.67 by 7 and 9 by (2). Also recently, there has been an improvement on lower-bounds for approximating Continuous MEDIAN and K-MFANS where centers can be picked anywhere in the real space. By Cohen-Addad, Karthik, and Lee [5). it is NP-hard to approximate Continuous k- k-MEDIAN and k-MEANS within factors 2 o(1) and o(1) respectively.
FAIR-K-CENTER is a special case of Priority k-CENTER where the radii r(v) in which point demands center at that distance, are general values. possible 2- 2-approximation. Gørtz and Wirth [8] study the problem for asymmetric metrics and prove that it NP-hard to obtain any non non-trivis trivial approximation. [5] give a-approximation for the problem in presence of outliers and further generalize to constant approximations for general constraints on the solution centers. Another very closely related problem Chance-k-Coveree in which for any point in addition to r(v), probability p(v) is given and the goal is to find distribution on possible solutions such that a solution drawn from this distribution covers e with probability at least p(t). This also has a 9-approximation by [20].
[2 introduced this problem and gave best
introduced in [20]
clustering problem related to FAIR-K-MEDIAN and FAIR-K-MEANS is the Simultaneous k- Clustering in which the goal is to find a solution with approximation guarantees with respect to any monotone, symmetric norm. This problem has an approxxaxiinoonnn due to Chakrabarty and Swany with line of previous work including 3 10 8].
Another similar notion of individual faimesss is introduced by Chen et al. [3] in which solution is fair if there is no group of size at least n/k for which there exists a facility that would reduce the connection cost of all members of the group if opened.
[33] give a (1 + ++v22 apppppoooinn for f, (2, and foc norm distances for the setting where facilities can be places anywhere in the real space. Micha and Shah (30) modified the approach to give close to 2-approximation for & and proved the previous results for & and & are indeed tight.
Recently, Abbasi et al. [ introduced new notion of fairness centered around providing equitable group representations. In this problem, the points partitioned into groups and the goal is to minimize the maximum clustering cost a group can have the solution. The idea is that the cluster centers should represent each group fairly, and this is captured by ensuring that each group's clustering cost is comparable with the others. This notion is orthogonal to the fairness criteria we study in this paper; Although we could tune the maximum distance the points in group have to our solution, that does not give any guarantees with respect to the objective cost and vice versa.
2 Preliminaries
In this section, we formally define our problems, establish some notations, and describe a classic clustering routine due to Hochbaum and Shmoys [2]] with modifications by Plesník (32). Given a subset S [ X, we use d(v, S) to denote e's distance to the closest point in S.
Definition (FAIR (p, Je)- CLUSTERING Problem). The input is a metric space (X, d), radius function r : X- + R++ + and integers p, k Z The goal is to find S X of size at most & such that d(v,S) < rw)) for all e E X and the clustering cost (Eve d(v, SYP) 1/P minimized.
Let opt be the clustering cost of an optimal solution. For a, 3 2 1, an (a, appproxxiee solution is S SC X of size most with d(v, S ar(v) for all e X and ( (Eeex d(v. S)p) ")> 3opt. In plain English, the faimess approximation is a while the objective/cost approximation is 3. Our main result the following.
Theorem 1. There is an (8,2142/v) aaprrxiittttii algorithm for FAIR- (p, CLUUSTRRGG that runs in LP solving time plus Ö(n²), overall Ö(kn*).
The algorithm relies on rounding a solution to the following LP for FAIR-(p, k)- CLUSTTRRIN where the optimal LP objective is at most opt". The variable yo denotes the amount by which
Thh LP and its rounding is slightly different for p oot we omit this from this version.
3

---

is open as center. Teu for v, E X is the amount by which is assigned to The constraints respectively capture the conditions: every client must connect to someone, & centers are opened. no client can connect to an unopened center, and crucially that client cannot travel to center further than r(v).
opt
min Σ
d(v,u)Pan 2
(LP)
Tvu S yur
Vu, u E X
(LP3)
Tvu 1, VOE Σ
(LP1)
= 0, Vu, u d(v, u) > r(e)
(LP4)
Σ WEX
yhu =
(LP2) Tour Yu S 1,
Va, u X.
From here on, we use the notation B(u, r) for X and R+ to denote the points in ball of radius around u. That is Bu,, = fv E X d(u, v) S r}. Also, for any set of points U S X, let y(U)= = Enev Yu. Considering (LP4) and (LPI) the following holds.
*
Fact 1. If y is from feasible
LP solution, then y (Bu r())) 2 1 for all v D X.
We now describe routine Filter due [3 21 which is used as subroutine our main algorithm. Assume all the points are initially "uncovered". The routine takes a function R : X - RT sorts the points in order of increasing R(v)'s. Then considers the first point in this order, calls it "representative" and "covers" all the points v at distance at most 2r(v) from it. Call these points D(v). Repeating this procedure until all the points are covered, forms a partition on X such that the representatives are "far apart", while each ron-reerreentttive is assigned to a "nearby" representative, among other useful properties listed in Fact 2 and Fact
Algorithm 1 Filter
Input: Metric (X, d), radius function R : X R+
U X
The set of "uncovered points" The set of "representatives"
2: S
--0 0
3: while U + 0 do
4:
+ arg min R(v)
The first point in U in non-decreasing R order D(u) B(u, (R))) N and includes itself
5: S
6:
D(u) E U: d(u, 2R(U))
7:
U+U(((u)
8: end while
Output: S, (D(u))ue5)
Fact 2. 32 21 The following is true for the output of Filter: (a) Vu, E S, S,d(u, v) >
2 max R( u R(v)). (b) The balls (B(u, R(u)) : u E $) are mutually disjoint, (c) The set (D(u):
E S} partitions X, (d) Vu E Vu E D(u), R(u)= < R(v), and (e) Vu E S, Ve D(u), d(u,v) S 2R(v).
Fact For any u E and B(u, R(u)), the unique closest point in S to
Proof. Suppose otherwise. That is, there exists u S not equal to u s.t. d(w,v) < d(w, u). Then d(u, v) S d(u, w) + d(w, v) < 2d(w, u) < 2R(u) which contradicts Fact 2 as we must have d(u,v) v) 2 (())
To elaborate the importance of Algorithm 1 and build some intuition, we point the following theorem of 32 25
Theorem 2. Take S the output of Algorithm on a FAIR-(p, (p, k) -LLUSTEREG instance with R := r. Then if the instance feasible, [S] 2 and d( (v. S) < (v( for all v X.
Proof. By Fact we know that (D(u) E S} partitions X so for any X, there exists for which E D(u). Plus, d(v, u) S 2R(v) = 2r(x). Now only remains to prove |S] S To see this, let S* be some feasible solution and observe that two different E S, cannot be

---

covered by the same center in S Since otherwise, if there exists f E S for which f(u.f) r(u)
and d(w, f) - r(w) by triangle inequality d(u. v) < d(u. ) + d(f, w) S r(u) + r(o) and this
contradicts d(u, w) 2 max (ax()(())r(v) from Fact 2
But of course, the above theorem does not give any guarantees for the clustering cost (unless p = oo). It might be the case that many points are paying close to 0 towards the clustering cost in the optimal solution, but are made to connect to a point much farther the above procedure.
3 Algorithm for MAIR-(P, kt) A--CLUSTERINGG problem
Now we are ready to describe our algorithm Fair- which establishes Theorem At high- level, we run our Filter routine by defining the input function in a manner that is conscious of the FAIR-(P, KJ-CLUSTERING cost: given (x", v²") which is an optimal solution to (LP). for any V E X let C2 be v's contribution to the LP cost i.. Cg == Ewex d(v,, u)P
2in and define R(v)= == min(r(v), (2C.) Let us ponder for a bit to see what changes from Theorem 2 For the output S, we still have the fairnsss guarantee dv, S) < 2r(u) for all v but since (2C.) might be less than r(v) for any 2. we cannot guarantee that |S| S k. Thankfully, in this case, we can still prove |S| < 2 [Corollary 1). The rest of the algorithm is deciding on subset of at most & points out of this to return as the final solution, while ensuring the fairness and cost guarantees are still within constant factor of the optimal. This idea is very similar to existing ideas in 3 12 which look at the problem without fairness considerations.
Recall that (D(u)= u E }} partitions X and each u E S is responsible for covering all the points in D(u). Here, we could simply move each point in Duu)
and divert the y value of each point to its closest point in S. Note that, (S)) = k (Fact 4) and similar to the proof of Theorem 2 we could show you 2 1/2 Lemma 1) for all reaching 1. we open those centers.
hence |S S 2k (Corollary 1p. If this leads to some y-value
For u E S with yu < 1, if we do not decide to include it in the final solution, promise to open Su. its closest point in S other than itself. In this case, all the D(u) points on u are delegated to S.- Using the fact that yo < 1, can prove that faimess guarantee (Lemma 3) approximately holds for the points in D(u) even after this delegation.
To get the clustering cost guarantee, we need to do more work. Observe that, currently, is already fractionally assigned to v by 1 - Yu- So if instead of yu 2 1/2 we had ya = 1/2 we could ensure that already is assigned to by 1/2 thus integrally assigning u to only doubles the cost. This is why we need to do more work to get yu E {1/2, 1) for u e S (see Lemma 2} and then bound the clustering cost in Lemma 4
Fact 4. ySS) = k and remains so after Line 11
Proof. We initialize y to y" for which yx() = k by LP2 The algorithm then transfers y(X) to S by Line II without changing the total. Afterwards, the modifications in Lines 13 and 19 move the mass around in S but the total value vSS) remains unchanged.
Lemma 1. Liter 14 of Algorithm 2 1/2 S ya < 1 for all u S.
Proof. First we argue that yu Z 1/2 for all u E 5 by the end of Line 11 Fix u. E S. Per Fact 3 y( (B(u, R(u))) is entirely moved to ya. By definition of R(u) there are two cases: Case I. R(u) r(u) thus yu 2 as y" (B((,(()))) 2 1 for all u E X according to Fact 1 Case II, R(u) = (2C,) 1/P then by Markov's inequality yB(BBu, R(u))) Z 1/2 and after this point, Yo is never decreased to below 1/2. More precisely, C. ==== Evex d(u v v 2 Σ vex. d(u,v)P2t 2 R(n))))(())
2C,, Σ EEX:
The Considering Σvex 2tu- by LP1 this implies Σ VEX: 2 2 1/2 d(u.))s(u))
d(a.o)> thus y" R(a))) 2 1/2.
As for proving yr < might indeed be the case that yu > 1 by the end of Line but the loop ending at Line 14 can guarantee yo < 1 for all u E S. This is because v(S) = k FFcc 4b and we already checked in the beginning Algoorit 2 that |S]] k.
Corollary 1. S in Algorithm 2 has size at most 2k.
5

---

Algorithm 2 Fair-Round: FAIR-(P, kt CL.UTTERIG bi-criteria approximation
Input: Metric (X, d), radius function r: X - IRt, and (x" ./4)) an optimal solution of LP v's cost share in the objective
1: C. Evex d(u, s V E
2: R(e) t min(r(v), (20 Ve E
3: S. (.(()):
8) Filter((X,d).
4: if |s| I l then
5:
r
6: end if
7: (x,yy) +- (x", y*)
8: for all U E x do
b. Direct mass from outside of S to the closest point in S
9:
+ closest point in r
10:
- yo +0
b. Note: May cause to increase above 1
end for
12: while There are E S with ya > 1 and yo < do
Ensure S 1 for all E S Yu yu 6, yo - Yo + 6, where 8 min(1 you Yu 1}
14: end while
b Remark: By now, 1/2 S Yu I 1 for all u E S (see Lemma Vu S
S,, < closest point in S
16: while There are u, E S with
1/2 Yn < 1, and yo <1,
18:
> d(u, (v)) do
Move y mass from u to e if u is costlier
19: Yu f y/ 6. yo < yo + 8, where := min yo: yv. 1/2}
20: end while
P Remark: At this point, yh {1/2, 1 for all u E S (see Lemma 2
21: T T u E S with V/, =
22: Consider the forest of arbitrary rooted trees vertices E S with edges (u, Sw). Let O be
odd-level vertices in ST, . and be even-level vertices in SYT.
23: if | S [0] then
24:
T - P++UB TUE
25: else
26:
T + TUO
27: end if
Output: 7
Lemma 2. After Line 20 of Algorithm 2 Vu 11 for all S.
Proof. Suppose not. Since (SS) = k (Fact 4 and & is an integer, by Lemma there has to be at least u, S with Yu: Vo (1/ I) which is a contradiction, since either of them has to be changed to 1/2 or in the while loop ending at Line 20
Lemma 3. For all v E X, d(e, T) S 8r(u).
Proof. Fix v E X. Since (D(u)= E S} partitions X there exists u E S such that E D(u). According to Fact 2 (v, u) S 2R(v) S 2r(v) by definition of R. ends up 7 we are done. Else, it has to be that yo < and S, T. In what follows, prove that if yhe < 1 at Line 20 then d(u, S.) S (r().. This implies d(u, S.) E 8r(v) hence the lemma.
We know that initially y (BCc. r()))) 2 1 per Fact but since v & S, the mass on B(e, r(t)) has been moved S by Line 11 If for all of y(B(u, r(v))) would be moved to u then E Bl, r(v)) with x along with u' E S, u' * u. such that d(w, u') S d(w, u) which made Yw to be moved to u'. By definition of S., d(u, S.) < d(u, Applying the triangle inequality twice gives:
Bu, r())) their closest point in S was u, all 1 by the end of Line 20 So there must exist
d(u, Sw) S d(u, u') S d(u, w) + d(w, v/)
< 2d(u, w)
2(d(u, v) + d(v, w))
< 2(2r(v) + +())) Gr(v)
where the last inequality comes from Fact stating d(u, v) S 2r(v). and from fact that T implies d(e, w) r(v) by
LP4
Lemma 4. (Evex d(v. 1/ < ((2pt2) Exwex C.) 21+2/popt.

---

Proof. For the proof, we compare EvEx d(u, T with the optimal LP cost Evex C. which is at most opt". Fix v E X and u E S for which v E D(u). By Fact 2 d(v, u) I 2R(x) S 2(2C,) //P per definition of R. So moving D(u) to u for all u E S has an additive cost of Eves D() d(v, u)p I 2 20t1 Co. From now on, assume there are Duu) collocated points on a E S.
Moving around the y mass up to Line II adds a multiplicative factor of 2" loss in the approximation X in the LP solution, meaning, Fow 0 and Yw was moved to a u' E S (due to d(w, u') I d(wr, u)) then the cost u has to pay to connect to u' is d(u,, )² I (d(u, w) d(w, v'))² S 29d(u, w)² which is 2 factor worse than the LP cost d(u, w)P it was paying to connect to w earlier.
ratio. The logic is: if u S was relying on
At this point [Line 14), note that the cost incurred by u is (D(u) d(u, S.) v..) To elaborate on this, corresponding to y. we define an x such that (x; y) is feasible for LP Let Viu = you and
Tus, = =1- Vu so that LP4 satisfied for Then the cost incurred by is D (1) [dl (u, u)
S.,, zus.) = D S.,u, S,) - yu)) The while loop ending Line 20 does not increase the value of the objective function: As we decrease Yu and increase you only if the cost incurred by u is bigger than that of v. The last multiplicative factor 2 loss comes from when u. E S. In which case, Yu 1122 and S_ T. So by assigning to S., we pay ID(u)dd(u, S.)" which is twice more than before (as 1 Yu = 1/2). Observe that this last step is why we needed to do all the work to get Yu (1/2, 13 in Lemma 2 Putting the three steps together, the overall cost is at most 2 x 2D + 2 20-2 times the L. cost most 2pt2/ropt.
Proof of Theorem I Using Corollary and the fact that [T] - |S|/2 by construction, we have [T| S k. Lemmas 3 and 4 give the fairness and approximation guarantees. As for runtime, notice that Algorithm runs in time Ó(n²). But the runtime is dominated by the LP solving time, According
to [37. finding a (1 + + >-approximation to LP takes time Okkn² / Setting s = 1/7 gives the
(kn))) runtime.
As evident, the runtime is dominated by the L. solving time. We end this section by descibing the sparsification pre- preppeocessing that when applied the original instance, can tremendously decrease the solling time in practice while incurring only a small loss in fairness and clustering cost. One reason why the LP takes lot of time is because there are many variables; Tyu. for every v E X and every u within distance r(u) of v. To fix this, we first run the Filter algorithm on the data set with R(v) 8r(v), where is a tune-able parameter. It is not too hard to quantify the loss in fairness and cost as a function of 5, and we do so in the lemma below. More importantly, note that when 5 = 1, then the number of variables goes down from n to Olk); this is because of the definition of r(v) which guarantees R n/k k points in the radius r(v) around v. Therefore, running the pre-processing step would make the number of remaining points k. our experiments we set to be much smaller, and yet observe a great drop in our running times.
Algorithm 3 Sparsification + Fair-Round
Input: Metric (X, d). radius function r: X > R+ parameter 5 > 0
1: S, (D() u S - Filter((X, d), ōr)
2: (x',1)) t- solve LP only on points S with objective function Ee,ues d(v,,)) x) [(())
3: a t I Vu, w E X, E S : Duu) D e's assignment is identical to its representative
4: V t y if u E S and 0 otherwise
Output: Fair-Round d). (1 + 8)r, (x",""))
Lemma 5. Algorithm 3 outputs an (8(1 + 8), 2142/P +
where ø
(Erex (PpP))
Proof.
Observe that (x'. v²" is not a feasible LP solution anymore. Nevertheless, it will be feasible [
for when is dilated by a factor of (1 + 8) in the LP4 Here is how we argue LP4 holds in this case: For any w E X for which Th > 0, recall u E S is chosen so v E D(u) and x:w = I'y > 0
meaning d(u, w) S r(u). We have d(e, w) S d(v, u) + d(u, w) S 6r(v)+r(u) ( 8)r()) The
last two incqualities are by Fact 2 as d(c, u) S &r((v) and r(u) S r(t). As for the LP cost of (z" .y")),
7

---

it is not longer upper- bounded by opt" but rather by opt" + +Euss Dee d(v, u)P. This additive term is most Evex(ōr(v)) - (ōdopt)². Plugging this into Lemma 4 finishes the proof.
D
Experiments
Summary. We rum experiments to show that the empirical performance of our algorithms can be much superior to the worst-case guarantees claimed by our theorems (the codes are publicly availably on " While implementing our algorithm, choosing the constant "2" in [ine (definition of Rt in our algorithm, we perform a binary-search to determine better constant. Specifically, we find the smallest 3 for which Algooithm ggives at most k centers with R(v)= == (in(r(v), (BC,) for all v. This step is motivated by the experiments in [25]
make the following optimization instead of
We assess the performance with respect to (a) fairness, (b) objective value, and (c) running times. Due to space restrictions, we focus on the k- MEANS objective and leave k-MEDIAN results to Appendix B Our fairness violation seldom exceeds 1.3 (compare this to the theoretical bound of 8), and often much better than that of (29) and [25). The objective value of our solution is fact extremely
close to the LP solution, which is a lower bound on the optimum cost (compare this to the theoretical bound of 4). This occurs because typically the LP solution itself has many integer entries. Finally,
although the "vanilla" running time of the LP is pretty large, our sparsification routine Lemma tremendously reduces the running time.
Datasets. Similar to 29 we use datasets from the UCI repository 16
(also used in previous fair clustsering works of [14, 6). We use set of numeric features (matching previous work) to represent data Euclidean metric.
1- bank [35] with 4,521 points, on data collected by the marketing campaign of a Portuguese banking institution. We use 3 features "age". "balance". and "duration".
2- census (28) with 32,561 points, based on the 1994 US census. Here we use the following 5 features: "age" "final-weight", "education-nunc "capital-gain" and "hours-per-wer
3- diabetes 34 with 101,766 points, from diabetes patient records from 130 hospitals across US.
Benchmarks. We compare with the algorithms of 22 and 25 For 29 we set parameters according the experimental section of their paper. We remark that in their experimental section they perform swap in their local search instead of the 4-swaps for which they prove their theorem. For running time comparison, also compare with the popular k-Means+++ algorithm of [ from scikit learn toolkit [3] which has no fairness guarantees.
and the above two algorithm's running times
4.1 Fairness analysis
For any solution T C X, define the "violation array" 0T over E X as (r(c) d(v, /)/(()) This provides more fine-graine mne-griined view of the per-client fairness guarantee violation. Similar to (2]
we use maximum violation (i.e. max.ex 0r(u)) as a benchmark for fairness. In Figure 1 we have
plotted the maximum violation of our algorithm Fair-Round, 29 (noted as MV), and 25 (noted
as JKL). We find that our results are noticeably fairer than 29 while improving over 25 in many cases.
Next, we compare the histograms of the violation vectors 0 as described above. This picture provides better view of the fairness profile, as just looking at the maximum violation may not be robust measure; an algorithm that is largely unfair may be preferred to an algorithm that is extremely unfair on a single point but extremely fair on all the rest. We show the histograms of the violation vectors of these algorithms in Figure 2 (for full set of histograms see (ppeedixx I. As an example, even though in bank with k 20 our maximum violation is slightly worse than [25 our histogram shows that we are slightly fairer overall. We observe that our algorithm ensures complete fairness for at least 880 of the points almost all the experiments. A theoretical study of the violation vector interesting and left as future work.
https//arthii..ssss.cccee//aaaau
8

---

hant
dabeles
Maxemum tarness viste on 5
Fur-Round
MT
Number dlusters
Number
Namber clasters
Figure 1: Comparison maximum fairness violation with K-MEANS objective, between our algo- rithm Fair- Fair-Round, the algorithm in [25] (denoted as JKL), and the algorithm in (29 (denoted as MV), on average of 10 random samples of size 1000 each.
Round
Tall Ail-Roundeur
Mu of portss m1
Teir-iturra
hei--Bburra
Mu theneeeen poltte
Farness violatinn
Farmiss violaton
Figure 2: Histograms violation vectors on bank with k = 20 & M-MEA objective comparing Fair-Round with the algorithm in [25) (denoted as JKL) and the algorithm in [29] (denoted MV), on average random samples of size 1000 each.
4.2 Cost analysis
In Figure 3
demonstrate that in experiments, the objective value almost matches the optimal cost, begin at most % more almost always, and never above % 15 more than the LP cost. Note that cost is also higher than that of [29], and the reader may be wondering how the latter can be better than the optimum cost. The reason is that the [29] cost is violating the fairness constraint while the optimal cost is not. To do more apples-to-apples comparison, one also allow the same violations as [29] and re-solve the linear program and also our rounding algorithms. On doing so, we do find that our algorithm's cost becomes lower than that [29). Details of this can be found in (pppeedixx A.2 The set-up also allows us to measure the cost of fairness: how much does the linear programming cost and our algorithm's 's cost decrease as we relax the fairness constraints. We do this empirical study; see Appendix A.3 for our results.
census
diabetes
Raundound
Pair
4
JKL
121
Number clusters
Number of clusters
Number of custers
Figure 3: Comparison of MEMAN clustering cost, between our algorithm Fair-Round the algorithm in (25) (denoted as JKL), and the algorithm in [29] (denoted as MV), on average of 10 random samples of size 1000 each. We also plot the LP cost which is lower bound the optimum cost (denoted as Fair-LP.
Runtime analysis. We run our experiments Python 3.8.2 on MacBook Pro with 2.3 GHz 8-Core Intel Corei9 processor and 32 GB of DDR4 memory. We solve our linear programs using the Python API for CPLEX [22]. We demonstrate that even though solving an LP on entire instance is time consuming, our sparsification step tremendously improves the runtime (Figure 4) while increasing the clustering cost or fairness performance by a only negligible margin (see) Appendix A.4 for the cost and fairness results). Below, the blue line with circles shows Fair-Round with "vanilla" LP

---

solver, and the green line with upside-dows down triangles Sparse-Fair-Round is the runtimes with the sparse LP solution.
bank
diabetes
Roundound
Rundine in seconds
e-means--
Number claters
Namber
Number Clusters
Figure 4: Comparison runtime with k-MEANS objective, between our algorithm Fair-Round, the algorithm in 25 (denoted JKL), the algorithm in [29] (denoted MV), and k-Means average of 10 random samples of size 1000 each. Here, ô = 0.3, 0.05 and 0.01 for bank, census, and diabetes. Note that [25]. k-Means++5 and our sparsified algorithm Sparse- Ceirse-Fair-ie Faasee--FiRRRonddd Round have very small differences in their running times.
References
[1] Mohsen Abbasi, Aditya Bhaskara, and Suresh Venkatasubramannin. Fair clustering via equitable group representations. In Proceedings of the 2021 ACM Conference on Fairness, Accountability. and Transparency, FAccT 21, 2021.
[2] Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, and Justin Ward. Better guarantees for k-means and euclidean k-median by primal-dual dual algorithms. In Proceedings, IEEE Symposium on Foundations of Computer Science (FOCS), 2017.
[3] Soroush Alamdari and David B. Shmoys. A bicriteria approximation algorithm for the k-center and k-median problems. In WAOA, pages 66-75. Springer, 2017.
[4] David Arthur and Sergei Vassilvitskii. K-means++: The advantages of careful seeding. In Proceedings, ACM-SIAM Symposium on Discrete Algorithms (SODA), 2007.
[5] Tanvi Bajpai, Deeparab Chakrabarty, Chandra Chekuri, and Maryam Negahbani. Revisiting priority k-center: Fairness and outliers. Proceedings, International Colloquium on Automata, Languages and Programming (ICALP), 2021.
[6] Suman Bera, Deeparnab Chakrabarty, Nicolas Flores, and Maryam Negahbani. Fair algorithms for clustering. In Adv. in Neural Information Processing Systems (NeurIPS), pages 4954 4965. 2019.
[7] Jaroslaw Byrka, Thomas Pensyl, Bartosz Rybicki, Aravind Srinivasan, and Khoa Trinh. An improved approximation for k-median, and positive correlation in budgeted optimization. In Proceedings, ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 737-756, 2014.
[8] Jaroslaw Byrka, Krzysztof Sornat, and Joachim Spoerhase. Constant-factor approximation for ordered mediaa. In Proceedings, ACM Symposium on Theory of Computing (STOC), pages 620-631, 2018.
[9] L. Elisa Celis, Damian Straszak, and Nisheeth K. Vishnoi. Ranking with Fairness Constraints, In Proceedings, International Colloquium on Automata, Languages and Programming (ICALP), pages 28:1-28:15, 2018.
[10] Deeparnab Chakrabarty and Chaitanya Swamy. Interpolating between k-median and k-center: Approximation algorithms for ordered k-median. In Proceedings, International Colloquium on Automata, Languages and Programming (ICALP), pages 29:1 29:1-29:15 14, 2018.
[11] Deeparnab Chakrabarty and Chaitanya Swamy. Approximation algorithms for minimum norm and ordered optimization problems. In Proceedings, ACM Symposium on Theory of Computing (STOC), pages 126-137, 2019.
10

---

[12] Moses Charikar, Sudipto Guha, Éva Tardos, and David B Shmoys. A constant- ap- proximation algorithm for the k-median problem. Journal of Computer and System Sciences, 65(1):129-149, 2002.
[13] Xingyu Chen, Brandon Fain, Liang Lyu, and Kamesh Munagala. Proportionally fair clustering. In Proceedings, International Conference on Machine Leanring (ICML), volume 97, pages 1032-1041, 2019.
[14] Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii. Fair clustering through fairlets. In Adv. in Neural Information Processing Systems (NeurIPS), pages 5029-5037, 2017.
[15] Vincent Cohen-Addad, C. S. Karthik, and Euiwoong Lee. On approximability of clustering problems without candidate centers. In Proceedings, ACM-SIAM Symposium Discrete Algorithms (SODA), 2021.
[16] Dheeru Dua and Casey Graff. UCI machine learning repository, 2017.
[17] Teofilo Gonzalez. Clustering to Minimize the Maximum Intercluster Distance. Theoretical Computer Science, 38:293 - 306, 1985.
[18] Inge Li Gørtz and Anthony Wirth. Asymmetry in k-center variants. Theoretical Computer Science, 361(2-3): 2006. Preliminary version in APPROX 2003.
[19] Sudipto Guha and Samir Khuller. Greedy strikes back: Improved facility location algorithms. In Proceedings, ACM-SIAM Symposium on Discrete Algorithms (SODA), page 649-657, 1998.
[20] David G. Harris, Shi Li. Thomas Pensyl, Aravind Srinivasan, and Khoa Trinh. Approximation algorithms for stochastic clustering. Journal of Machine Learning Research, 103133): 2019. Preliminary version in NeurlPS 2018.
[21] Dorit S. Hochbaum and David B. Shmoys. A best possible heuristic for the k-center problem. Math. Oper. Res., 10(2):180-18) May 1985.
[22] IBM. Ibm ilog cplex 20.1. 2021. Free academic edition.
[23] K. Jain and V. V. Vazirani. Approximation algorithms for metric facility location and k- median problems using the primal-dual schema and lagrangian relaxation. Journal of the ACM, 48(2):274-29)) 296, 2001.
[24] Matthew Joseph, Michael Kearns, Jamie H Morgenstern, and Aaron Roth. Fairness in learning: Classic and contextual bandits. In Ady. in Neural Information Processing Systems (NeurIPS), pages
2016.
[25] Christopher Jung, Sampath Kannan, and Neil Lutz. Service in your neighborhood: Fairness in center location. In Proceedings, Foundations Responsible Computing, FORC 2020, volume 156, pages 5:1-5:15, 2020.
[26] Toshihiro Kamishima, Shotaro Akaho, Hideki Asoh, and Jun Sakuma. Fairness-aware classifier with prejudice remover regularizer. Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 35-50, 2012.
[27] Tapas Kanungo, David M Mount, Nathan Netanyahu, Christine D Piatko, Ruth Silverman, and Angela Wu. An efficient k-means clustering algorithm: Analysis and implementation. IEEE transactions on pattern analysis and machine intelligence, 24(7):881-89) 892, 2002.
[28) Ron Kohavi. Scaling up the accuracy of naive-bayes classifiers: A decision-tree hybrid. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 1996.
[29] Sepideh Mahabadi and Ali Vakilian. (individual) faimnss for k-clustering. Proceedings, International Conference Machine Leanring (ICML), pages 7925-7935, 2020.
[30] Evi Micha and Nisarg Shah. Proportionally fair clustering revisited. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), 2020.
11

---

[31] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, Prettenhofer, R. Weiss, V. Dubourg. J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and F. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 2011. Open source, commercially usable- BSD license.
[32] Ján Plesník. heuristic for the p-center problems in graphs. Discrete Applied Mathematics, 17(3):263 268, 1987.
[33] Clemens Rösner and Melanie Schmidt. Privacy Preserving Clustering with Constraints. In Proceedings, International Colloquium on Automala, Languages and Programming (ICALP), pages 96:1-96:14 2018.
[34] Beata Strack. Jonathan DeShazo, Chris Gennings, Juan L Olmo, Sebastian Ventura, Krzysztof J Cios, and John N Clore. Impact of hbale measurement on hospital readmis- sion rates: analysis of 70,000 clinical database patient records. BioMed research international, 2014, 2014.
[35] Paulo Rita Sérgio Moro, Paulo Cortez. A data-driven approach to predict the success of bank telemarketing. Decision Support Systems, 2014.
[36] Ke Yang and Julia Stoyanovich. Mcasuring fairness in ranked outputs. In Proceedings, International Colloquium Automata, Languages and Programming (ICALP), page 22. ACM, 2017.
[37] Neal E. Young. Sequential and parallel algorithms for mixed packing and covering. In 42nd Annual Symposium on Foundations of Computer Science, FOCS, Las Vegas, Nevada, USA, pages 538-546, 2001.
[38] Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez-Rodriguez, and Krishna P. Gummadi. Fairness constraints: Mechanisms for fair classification. Proceedings, International Confer- ence on Artificial Intelligence and Statistics (AISTATS), pages 962-970,2000
[39] Rich Zemel, Yu Wu, Kevin Swersky, Toni Pitassi, and Cynthia Dwork. Learning fair representa- tions. In Proceedings, International Conference on Machine Leanring (ICML), pages 325-333, 2013.
12


Reviews:
[{"review_id": "pynxkC2cLMr", "reviewer": "Reviewer_UP3J", "summary": "This paper introduces a new algorithm for fair k-clustering problem(specifically when cost is measure with l_p norm for different p values) based on LP rounding. It provides a bi-criteria approximation guarantee for the clustering objective and experiments are provided to validate the theoretical properties. It is also shown how the runtime of the algorithm can be improved using sparsification with minimal effects on the objective.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "# Originality\n\nAlthough LP formulations have been studied for various clustering settings under different constraints, this paper introduces a nice formulation that handles fairness constraints and I believe that the rounding procedure and the analysis contain a decent amount of original work. \n\n# Quality\n\nThe quality of the writing and the presentation are good. This result has been placed among the relevant prior work well. The experiment complements the theoretical guarantees provided.\n\n# Clarity\n\nThe clarity of the paper for the most part is good. However, I believe the following places need more clarification.\n- In the experiments, when looking at the violations, what is considered the ground truth clustering? Do the datasets have cluster labels and if so do they adhere to the k-means(or k-median) optimal clustering? or output from some standard algorithm(eg: k-mean++) is considered the ground truth?\n- It is not clear why Fact 4. in line 186 hold. Don't the updates in Algorithm 2, line 13 or line 19 affect that condition on y?\n\n# SIgnificance\n\nFair k-clustering is an important problem for the NeurIPS community in my opinion and the improvements on the running time and the approximation guarantees simultaneously for the clustering objective and fairness (where prior works are lacking) carries a substantial significance.\n\nOverall, I believe this paper adds decent contributions.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Some limitations are discussed regarding the theoretical analysis of violation vectors.\nIt may be worthwhile comparing this work with other notions of fair clustering, for example when the objective is maintaining similar cost for every cluster (see \"Fair Clustering via Equitable Group Representations\" by Abbassi, Bhaskara, and Venkatasubramanian).\n", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "lWRh_nrcRV", "reviewer": "Reviewer_RN5f", "summary": "The authors of this paper consider the individual fair k-clustering problem, as introduced by Jung et al. [FORC 19]. In this model, for every point $j$ there is a given radius $r_j$, and the goal is to choose a set of centers such that each point has an open center within distance $r_j$ from it, and also one of the standard clustering objective functions is minimized.\n\nSpecifically, under the k-median and k-means objectives, the authors provide improved guarantees compared to the state of the art results (Mahabadi and Vakilian [ICML 2020]). For the k-median objective, they give an $(8,8)$-bicriteria algorithm, while the best known result was an $(84,7)$ one. For k-means their result is an $(4,8)$-bicriteria algorithm, while the result of Mahabadi and Vakilian was a $(\\gamma,7)$ one, with $\\gamma$ being a very large constant. (an $(a,b)$-bicriteria solution has objective cost at most $a$ times the optimal, and for every $j$ it has an open center within distance at most $b \\cdot r_j$ from it).\n\nThe authors achieve their results via standard LP-rounding techniques.", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "A COMMENT ON A PREVIOUSLY OVERLOOKED TRIVIAL SOLUTION:\n\nBefore I proceed with my actual review, I would like to make an observation regarding this particular fair clustering problem.\n\nI remember after reading the Mahabadi and Vakillian paper, it was obvious to me that their local-search approach (although technically sound and very impressive) was unnecessarily complicated and far from efficient (in terms of the approximations achieved). Specifically, there is a trivial LP-based approach that can immediately give refined results. Focus on k-median for instance, and consider the standard LP for it with the additional constraint that $D_j = \\sum_{i}x_{i,j} \\cdot d(i,j) \\leq r_j$, where $D_j$ is basically the fractional assignment of point $j$. Then any deterministic LP rounding approach that satisfies $\\sum_{i}\\hat{x}_{i,j} \\cdot d(i,j) \\leq \\rho D_j$, would immediately yield results for the fair problem as well (here $\\hat{x}$ is the integral assignment after the rounding). For instance, the rounding from \"A Dependent LP-rounding Approach for the k-Median Problem\" by Charikar and Li would give $\\rho = 9$ and subsequently an $(9,9)$-bicriteria algorithm (I'm actually referring to the bundling process they use to solve matroid-median). In case I'm missing something (though I have discussed this with a couple fellow researchers), it's surprising how such a trivial solution was overlooked by Mahabadi and Vakillian.\n\nCLARITY OF THE PAPER:\n\nThe paper is very easy to follow and the authors have done a great job with regards to writing. I really enjoyed reading this work.\n\nCORRECTNESS:\n\nI went though all the arguments as carefully as I could, and I believe that all the theoretical claims are sound.\n\nSIGNIFICANCE - ORIGINALITY:\n\nThe main contribution of this work is improved results compared to the Mahabadi and Vakillian paper. However, I think that a more accurate comparison is with the trivial solution I mentioned earlier. Compared to that, the authors employ their own rounding approach, instead of just using another one as a black-box. This gives indeed an improvement, but under this comparison the refinement is not that substantial. Moreover, I don't think that the details of their technique are very novel, since similar rounding ideas have appeared before. \n\nOverall, we have a problem that has a trivial solution which was overlooked by the previous \"state-of-the-art\" results. Compared to the trivial solution, the authors indeed provide refined results, yet 1) the improvement is not that substantial and 2) the techniques used are not really original. Nonetheless, it would be beneficial (to the research community) if the results of this paper are published, since they show a much more accurate algorithmic understanding of the problem (compared to the Mahabadi and Vakillian paper). My concern is that they might not be novel enough technique-wise to meet the high NeurIPS threshold.\n\nMINOR COMMENT REGARDING THE EXPERIMENTS:\n\nTo test the scalability of the sparsification process it would have been better to run for a larger sample of points (1000 points seem already too few).\n\nMOTIVATION:\n\nWhen this model was first introduced I was skeptical about it, in the sense of believing that it doesn't actually capture any notion of fairness. It felt more like a robust version of k-median/k-means, where you want to give an additional covering guarantee to each client. From my perspective, Jung et al. did not do a good job justifying the fairness aspect of the problem (same thing with Mahabadi and Vakillian, although this was justified in the sense of them studying an already established model). \n\nMy issue stems from the fact that this notion of individual fairness diverges from the definition given by Dwork et al. in their seminal work \"Fairness through Awareness\" [ITCS 2012] (a solution is individually fair iff it treats similar points similarly).\n\nI understand that the authors did not have to justify the model from a fairness perspective, since it is an already established one, and hence I reviewed their paper based only on its own merit without letting doubts of the model affect my judgement. However, because previous work lacks a convincing discussion on why this particular constraint captures fairness, it would be beneficial to the community if someone does this. Therefore, I recommend that the authors add a detailed discussion about this in their paper.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours reading the paper + 1 hour thinking about the review + 1 hour writing the review"}, "extra_text": {}}, {"review_id": "c7dErcNx5TP", "reviewer": "Reviewer_mdjA", "summary": "This submission proposes an approximation algorithm for individual fair k-clustering in a metric space. Here, individual fairness means that each point v has an individual radius $r(v)$ and we require an open facility within radius $r(v)$ of $v$. We may use the radius $r(v)$ to provide each point $v$ with a \"fair share\" of its assigned facility by, for instance, choosing $r(v)$ as the smallest radius such that $n/k$ points lie within radius $r(v)$ of $v$; as originally proposed by Jung, Kannan, and Lutz. \n\nThe approximation algorithm is the main contribution of the submission. It works for any p-norm objective and is bi-criterial, guaranteeing an $2^{1+2/p}$-approximation of the  objective while ensuring an open facility within radius $8r(v)$ of each point $v$. However, it requires a metric space which means, in particular, that all facilities/centers have to be chosen from the point set.\n\nThe algorithm roughly works in the following way: First, the authors compute an optimum solution to a linear programming relaxation of the problem. The solution is turned into an input for a filter function by Plesnik/Rita, Moro and Cortez; this function replaces the original point set by a smaller set of representatives. In the original version of the filter, the function may be run until only $k$ representatives remain (a point may represent another if it can serve as the point's facility; hence, in the original filter, the representatives are then chosen as the facilities to open). In this case, however, it may be that the filter stops early as the fairness restriction on the connection radius may make it impossible to cover all points with $k$ representatives. Hence, a final step is required to reduce the set of representatives down to $k$ points. This is done via an LP-rounding algorithm and turns out to be a substantial amount of work. Finally, in order to improve the running time of the algorithm, the authors propose a sparsification technique for the LP-relaxation (whose size is otherwise quadratic in the number of points and could be prohibitive for larger point sets).\n\nAn empirical part shows improvements over the previous approach.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "The paper is exceptionally well written and I found it good to follow even through the substantial technical parts. The authors state that their work is mostly a combination of existing ideas. I feel this is a rather modest description and found the work to be quite non-incremental. I particularly like how the existing approach is extended to the individual fairness model in a non-trivial way. The experimental part is extensive; certainly larger than I would have expected for a paper with a sizeable theoretical contribution. The sparsification shows that clearly practicability was a priority for the authors.\n\nAs the weaker sides of the submission, I only see the assumption that all facilities must be chosen from the input points; the  approximation results for k-means (l2-objective, in language of the paper) from the literature generally assume a Euclidean space and permit the use of non-input points as facilities. The cited reference [1] considers Euclidean k-median. The assumption may be removed, but only at the loss of a factor of 2 in the approximation guarantee. \n\nThis is not so much of a limitation, but the distinction could be more explicit in the paper. In particular, having a decent LP-rounding and sparsification for Euclidean k-means without having to invest a factor of 2 would be a big result.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See above; it would like the submission to be more explicit about having to choose the centers/facilities from the input points.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "35bWBJnopn_", "reviewer": "Reviewer_XHqy", "summary": "The paper studies the problem of \\ell_p norm and center-based clustering with a\nfairness consistent. The fairness constraint roughly says that no point should\nbe further from its assigned center than it is from its (n/k)-th furthest\nneighbor. The authors consider a Linear Programming based (approximation)\nalgorithm for this problem.\n", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Center based clustering is widely studied problem where the basic problem of\nclustering, i.e. partitioning data is framed as a combinatorial optimization\nproblem of picking k centers such that some combination of the distance of the\npoints from their nearest center (typically the sum -- though can be max in the\ncase of k-center) is minimized. These problems are well-studied -- most of them\nare NP-hard, and in several cases approximation algorithms to some factors are\nknown. There are also hardness of approximation results known for several\nsettings -- though some gaps in our understanding remain. Since the main\npurpose of the paper is not to discuss these problems per se, this should\nsuffice for the purpose of this review.\n\nThe goal in this paper is to have an additional \"fairness\" constraint -- where\nfor each point v in the dataset, there is a quantity r(v) and the requirement\n(hard constraint) is that the center assigned to v should not be at a distance\nof more than r(v) from this point. Of course, in some cases this may be\nimpossible and relaxations can be considered. There is also the standard k-*\nobjective, where * can be median, mean, center etc. Let me call these\nobjectives A (radius r(v)) and B cost of the k-* value. Then an (\\alpha, \\beta)\nbi-criteria approximation algorithm guarantees that the distance of v from its\nassigned center is no more than \\alpha r(v) and also that the overall cost of\nthe objective B for the k-* value is no more than \\beta OPT. \n\nThe authors design LP-based algorithms that can achieve \"better\" bi-criteria optimization algorithms that were available in prior work. \n\nThe main shortcoming I see in this work is that this particular criterion has been proposed very recently, as recent as 2020, and in particular the authors don't explain very well why this is an interesting objective to consider. In fairness, the authors do say that their focus is on the \"algorithmic\" rather than the fairness part of the work, but it is not clear to me that this is necessarily an interesting algorithmic problem to solve if the fairness objective is not well-motivated enough, and the authors do little to motivate it. Furthermore, the actual algorithmic techniques are not particularly novel or impressive, though it does improve on the current state of affairs. Thus, I am relatively lukewarm about this paper.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See above for limitations. \n\nRegarding societal impact, while I think there is inadequate discussion about it in the paper, I don't hold this against the authors. It's not clear what is to be expected from a paper like this.\n", "review_text": "", "extra_scores": {"ethical_concerns": "There are none.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors consider the problem of \ell-p objective (e.g. k-median, k-means) centre based clustering with fairness constraints. The notion of fairness is that no point v should be at a distance of more than r(v) from its respective centre (where there are some conditions on r(v) to ensure feasibility). This notion of fairness was introduced in prior work and the authors main contribution is algorithmic. The algorithmic techniques while standard do improve on the (very recent) state of the art; thus the paper could be of interest to the NeurIPS community. There was a lot of discussion about the notion of fairness as well. It is suggested that the authors critique the notion (from all angles) more effectively, given how new this notion is, in order for the paper to have the most influence.
Decision: Accept (Poster)