Constant-Factor Approximation Algorithms for Socially Fair $k$-Clustering
Authors: Mehrdad Ghadiri
Mohit Singh
Santosh Vempala
Venue: Submitted to ICLR 2023 (2023)
Keywords: Clustering
k-means
fairness
approximation algorithms
iterative rounding

Abstract: We study approximation algorithms for the socially fair $(\ell_p, k)$-clustering problem with $m$ groups which include the socially fair $k$-median ($p=1$) and $k$-means ($p=2$). We present (1) a polynomial-time $(5+2\sqrt{6})^p$-approximation with at most $k+m$ centers (2) a $(5+2\sqrt{6}+\epsilon)^p$-approximation with $k$ centers in time $(nk)^{{2^{O(p)} m^2}/\epsilon}$, and (3) a $(15+6\sqrt{6})^p$ approximation with $k$ centers in time $k^{m}\cdot\text{poly}(n)$. The former is obtained by a refinement of the iterative rounding method via a sequence of linear programs. The latter two are obtained by converting a solution with up to $k+m$ centers to one with $k$ centers by sparsification methods for (2) and via an exhaustive search for (3). We also compare the performance of our algorithms with existing approximation algorithms on benchmark datasets, and find that our algorithms outperform existing methods.

Under review as a conference paper at ICLR 2023
CONSTANT-FACTOR APPROXIMATION GORITHH FOR SOCIALLY FAIR K- CLUSTERING
Anonymous authors Paper under double-blind review
ABSTRACT
We study approximation algorithms for the socially fair (lp, clluserrinn problem with m groups which include the socially fair k-median (p 1) and k-means (p 2). We present (1) polynomial-time (5 + (a./6//aappoxiimatoo with most k + centers (2) (5 + 2v6 + c)" approxpooinntoo with i centers in time (nk))200mm²/ and (3) a (15 + 6/)) approximation with centers in time km poly(n). The former obtained by refinement of the iterative rounding method via a sequence of linear programs. The latter two are obtained by converting a solution with up to + m centers one with & centers by sparsification methods for (2) and via an exhaustive search for (3). We also compare the performance of our algorithms with existing approximation algorithms on benchmark datasets. and find that our algorithms outperform existing methods.
INTRODUCTION
Automated decision making using machine learning algorithms being widely adopted in modern society. Examples of real-world decision being made by ML algorithms are innumerable and include applications with considerable societal effects such as automated content moderation Gorwa et al.) (2020) and recidivism prediction Angwin et al. (2016). This necessitates designing (new) machine learning algorithms that incorporate societal considerations, especially fairness Dwork et al. (2012);
Kearns and Roth (2019).
The facility location problem is a well-studied problem in combinatorial optimization. Famous instances include the k-means, k-meddan and k-center problems. where the input is a finite metric and the goal is to find & points ("centers" or "facilities") such that a function of distances of each given point its nearest center is minimized. For k-means, the objective is the average squared distance to the nearest center; for k-median, it is the average distance; and for k-center, it is the maximum distance. These all captured by the (fp, k)-clusterinng problem, defined follows: given a set of clients A of size n,, a set of candidate facility locations F, and a metric d, find a subset F F of size k that minimizes ΣieA d(i, F)P, where d(i, F) minge F d(i,j). This is NP-hard
for all p. and also hard to approximate Drineas et al. (2004): Guha and Khuller (199). A 20(p).
approximation algorithm was given by [Chrrikar et al. (2002 The current best approximation factors for k-median and k-means on general metrics are (2.675 + <>-approximation Byrka et al. 2014) and (9 + -)pprooxxiittion Kanungo et al. (2004); Ahmadian al. (2019), respectively.
Here we consider socially fair extensions of the (L,, k)-clusteringg problem in which m different (not necessarily disjoint) subgroups, A Ai U... U A... among the data are given, and the goal is to minimize the maximum cost over the groups, so that common solution is not too expensive for any one of them. Each group can be a subset of the data or simply any nonnegative weighting. The goal is to minimize the maximum weighted cost among the groups, i.e..
min FCF:
max EiEA, (.)i) .c(m)
=
weighting of (1) 1/| for E A,, corresponds to the average of groups. The groups usu- ally arise from sensitive attributes such as race and gender (that are protected against discrimination
In some other works, the p'th root of the objective is considered and therefore the approximation factors look different in such works.

---

Under review as a conference paper at ICLR 2023
under the Civil Rights Act of 1968 Hutchinson and Mitchell (2019) Benthall and Haynes 2019)
The cases of p = and = 2 are the socially fair k-median and k- k-meass, respectively, introduced by /Ghadiri et al. (2021): ; Abbasi al. (02T). As discussed in Ghadiri al. (202I), the objective of
the socially fair k-means promotes a more equitable average clustering cost among different groups.
The objective function of socially fair k-median was first studied by Anthony et al. (2010) who gave an O(log mlglog -pprroxiiiatonnn algorithm. Moreover, the existing approximation algorithms for the vanilla k-means and k-median can be used find (mm)appproximate solutions for the socially fair versions Ghadiri et al. (202T); Abbasi et al. (202T). The proof technique directly yields a m 20()) (pp'>approxiittionn for the socially fair (c.. k) k)-clustering. The natural linear programming (L.P relaxation of the socially fair k-median problem has an integrality gap of (m)) Abbasi et al. 2021
More recently, Makarychev and Vakilian (202T) strengthened the LP relaxation of the socially fair (b,, k)-clustering by a sparsification technique. The stronger LP has an integrality gap of Mllog m/ log log l)) and their rounding algorithm (similar to Charikar et al. (2002)) finds a (20(p) log m/ log log m)) -aprrooxxiiaaoonn algorithm for the socially fair (fp, -))cceutern For the socially fair k-median, this is asymptotically the best possible in polynomial time under the assump- tion NP & Ns50 DTIME((2") BBhattacharya et al. (014)). Due to this hardness result, it natural to consider bicriteria approximation, which allows for more centers whose total cost is close to the optimal cost for & centers. For the socially fair k-median and 0 < c << 1, Abbasi et al. (202I) presents an algorithm that gives at most k/ ee) centers with objective value at most 20(p) e times the optimum for k centers. Our first result is improved bicriteria approximation algorithm for the socially fair& lp clustering problem with only m additional centers (m is usually a small constant).
Theorem 1.1. There is a polynomial-tin -tmme bicriteria approximation algorithm for the socially fair (Cp, k)- -clustering problem with m groups that finds a solution with most k + centers of cost at most (5 + 2/ ze 9.9º times the optimal cost for a solution with l centers.
2022 show that a solution to the socially fair (lp, k)- clustering problem with K >> A centers and cost C' can be converted to a solution with k centers and cost at most 3p (C' + 2opt) ) by simply taking the k-subset of the k' centers of lowest cost. A proof is in the appendix for completeness. We improve this factor using sparsification technique.
Goyal and Jaiswal Goyal and Jaiswal
Theorem 1.2. For any c > O, there is a (5 (1e++//6=))-aapppp approximaation algorithm for the socially fair (Ep: k) -clustering problem that runs in time (nk) 200m) /e; there is a (15 + -aprroippoiinnioonnn algorithu that runs in time km poly(n).
This raises the question of whether faster-constant--actoo approximation is possible. Goyal and Jaiswal (2021) show under the Gap-Exxpoential Time Hypothesi is hard to approximate socially Tair k-median and k-means within factors of 1 + 2/e- - and + +8/e respectively, in time g(k)- (m)) for f.g: R+ + Rt; socially fair (ep. k) -clustteri is hard to approximate within factor of 30-c - e in time g(k)-n (M), They also give a (3 + apprrxiiimttoo time (k/e))(k) poly(n/c). This leaves open the possibility of a constant- factor approximation in time f (mm) k).
For the case of p + oc, the problem reduces fair k-center problem if we take thh root of the objective. The problem is much better understood and widely studied along with many general- ization Dia et al. (202T): (Anegg al. (202T): Makarychev and Vakilian (202T). Makarychev and Vakilian 2021 result implies an O(1) -aprroximation in this case.
We compare the performance of our bicriteria algorithm against Abbasi et al. (02T) and our algo- rithm with exactly l: centers against Makaaychev and Vakilian (022) on three different benchmark datasets. Our experiments show that our algorithms consistently outperform these in practice (Scc- tion 5) and often select fewer centers than the algorithm of Abbasi et al. (2021) (Section E.3
1.1 APPROACH AND TECHNIQUES
Our starting point is I.P relaxation of the problem. The integrality gap of the natural I. relaxation m Abbasi et al. (20TT). For our bicriteria result, we use an iterative rounding procedure, inspired
p Informally Gap-ETH states that there is no 20(m) algorithm to distinguish between satisfiable for- mula and formula that is even (1 -e) satisfiable.
2

---

Under review as a conference paper at ICLR 2023
by Krishnaswamy et al. (2018). In each iteration, solve LP whose constraints change from one iteration to the next. We show that the feasible region of the final LP is the intersection of matroid polytope and m affine spaces. This implies that the size of the support of an optimal extreme solution is at most k + m - see Lemma 1.3 Rounding up all of these fractional variables results in solution with l m centers.
There are two approaches to convert a solution with up to k + m centers to a solution with centers. The first is to take the best k-subset of the k + m centers which results in a (15 + --6)". approximation for an additional cost of O(k" + m)) in the running time. This follows from the work of Goyal and Jaiswal (021). For completeness, we include it as Lemma A. in the Appendix.
The second approach is to "sparsify" the given instance of the problem. We show if the instance is "sparse," then the integrality gap of the LP is small. A similar idea was used by Li and Svensson (0116) for the classic k-median problem. We extend this sparsification technique clustering. We define an a-sparse instance for the socially fair k-median problem as an instance in which for an optimum set of facilities O, any group solution, the number of clients of group in a ball of radius d(i, O)/3 centered at i is less than Aal For such an instance, given a set of facilities, replacing facility with the closest facility to 2d(E.O)
socially fair
[m]] and any facility i not in the optimum
i in O can only increase the total cost of the clients served by this facility by constant factor plus 2a. We show that if an instance is O (2R )-sparse, then the integrality gap of the LP is constant.
For an O(opt/m) ((opt//m-spprse -sparse instance of the socially fair k-median problem, a solution with + m centers can be converted to solution with ls centers in time n ((m")) while increasing the objective value only by constant factor. Our conversion algorithm is based on the fact that there are at most Omm²) facilities that are far from the facilities in the optimal solution. We enumerate candidates for these facilities and then solve an optimization problem for the facilities that are close to the facilities in the optimal solution. This optimization step is again over the intersection of the polytope of a matroid with ma half-spaces. In summary, our algorithm consists of three main steps.
1. We produce n (mm)) instances of the problem such that at least one is O ((tt)) >-sparse and its optimal objective value is equal to that of the original instance (Section 4 Lemma 3.2).
2. For each of the instances produced in the previous step, we find pseudo-solution with at most
k + m centers by an iterative rounding procedure (Section 2 Lemma(.II)
3. We convert each pseudo-solution solution with h + m centers to a solution with k centers (Section Lemma 4.2p and return the solution with the minimum cost.
1.2 PRELIMINARIES
We use terms centers and facilities interchangeably. For set S and item we denote Su(i} by Sti. For sets SI,..., Ss, we denote their Cartesian product by 8 JE(N] Sj. i.e., (.1,...,88) E 2 jE(H S and only if $1 E Si..... Sk E Sg. For an instance I of the problem, we denote an optimal solution of I and its objective value by OPT, and optz, respectively. A pair M = (E, I), where I is non-empty family of subsets of E, is a matroid if: 1) for any S C T F, if E I then S E I (hereditary property); and 2) for any 5, T E I, if |S| < [T], then there exists i E T S such that S+ic E I (exchange property) see Schrijver (2003). We call I the set of independent sets of the matroid M. The basis of M are all the independent sets of .M of maximal size. The size of all of the basis of matroid is equal and is called the rank of the matroid. We use the following lemma in the analysis of both our bicriteria algorithm and the algorithm with exactly ic centers.
Lemma 1.3. Grandoni et al. (2014) Let M = (E,I) be a matroid with rank k and P(M) denote the convex hull of all basis of M. Let Q be the intersection of P(M) with m additional affine constraints. Then any extreme point of Q has a support of size at most ls + m.
Related work. Unsupervised learning under faimess constraints has received significant attention over the past decade. Social faireess (i.e., equitable cost for demographic groups) has been consid- ered for problems such as PCA Samadi et al. (2018): Tantipongpipat et al. (2019). Other notions of fairness are also considered for clustering. The most notables are balance in clusters (i.e., equitable representation of groups) Chierichetti et al.] (2017); Abraham et al. (2000); ; Bera et al. (2019; Ah- madian et al. (2019), balance in representation (i.e., equitable representation of groups in selected centers)] Hajiaghyyi et al. (2010); KKishnaswamy et al. (20IT); Kleindessner et al. (2019), and indi-
vidual fairness Kleindessner al. (2020): Vakilian and Yalciner (2022): Chakrabarti et al. 2022))
3

---

Under review as a conference paper at ICLR 2023
However as shown by Gupta et al. (2020). different notions of fairesss are incompatible in the sense that they cannot be satisfied simultaneousl. For example, see the discussion and experimental result regarding incompatibility of social fairness and equitable representation in Ghadiri et al. (202T). In Chen addition, several other notions of fairness for clustering has been considered Chen et al. (
et al. 2020)); Mahabadi and Vakilian (000)) Micha and Shah (2020) Brubach al. (2020).
2 BICRITERIA APPROXIMATION
In this section, we prove Theorem T.1 Our method relies on solving a series of linear programs and utilizing the iterative rounding framework for the k-median problem as developed in Krishnaswamm et al. (2018); Gupta et al. (202I). We aim for cleaner exposition over smaller constants below. We use the following standard linear programming (LP) relaxation (LP1).
min 2 s.t. 22 EiEA,SEF (i)
(LP1)
min 2 s.t. 2 EjE,, EiEr, (o())d(i.))Pu,
(LP2)
V1 $ $ m, S; WijAje プjEドVi=1 = Σ ΣjeF Big byz =1 V. y, 2 0.
4A $ m, (2)
Σj =k Σ Ejer, yj v;= =1
(3)
vi A.
(4)
O.
Theorem 1.1 follows as a corollary Lemma 2.1
we can pick
all the fractional centers integrally. Observe that, once the centers are fixed, the optimal allocation of clients facilities is straight- forward: every client connects to the nearest opened facility.
1'
Dj
D2
Lemma 2.1. Let 0< There is polynomial time algo- rithm that given a feasible solution (æ. G. 2) to the linear pro- gram LP1 returns feasible solution (x', y 2²) where E! I ((1+2(1 + A)/X)(++)])* & and the size of the support of y' is at most m. The running time is polynomial in n and the logarithm of the distance of the farthest points divided by X.
(a)
Proof. We describe the iterative rounding argument to round the solution (i, J. 2). As first step, we work with an equivalent lin- ear program LP2, where we have removed the assignment vari- ables x. This can be achieved by splitting each facility j to the number of unique nonzero ž.j 's and setting the corresponding vari- able for these facilities accordingly, e.g., if the unique weights are Tij < ē2j < Tzj. then the corresponding weights for the facilities are T1j. Z22 Zıj. and رzن β2z and the weights of the con- nections between these new facilities and clients are determined accordingly as either zero or the weight of the facility.
(b)
Figure 1: (a) Distance of from the facilities of its rep- resentative v. (b) Solid and dashed circles are the balls cor- responding to representative (41)) and non-representative clients (et5), respectively.
Let F be the set of all (splitted) copies of facilities. Then we can assume Fig E {0.0g) By } for each j (where j e F). We set F; {jj E F āzj > O}. Note that F; could contain multiple copies of original facilities. Observe that LP2 has feasible solution (ğ, for this choice of F; for each i E A. Moreover, any feasible solution to LP2 can be converted to a solution of LP1 of same cost while ensuring that each client gets connected the original copy of the facilities in F,.
The iterative argument is based on the following. We group nearby clients and pick only one repre- sentative for each group such that if each client served by the facility that serves representative, the cost is at most ((1 (1+2(1 + X) 2)/A)(1+A)) 2. Moreover, we ensure that candidate facilities F; for representative clients are disjoint. this case, one observes that the constraints Eq. Eq in LP2 define the convex hull of partition matroid and must be integral. Indeed, this already gives an integral solution to the basic k-median problem. But, in the socially fair clustering problem, there are m additional constraints, one for each of the m groups. Nevertheless, by Lemma [.3] any extreme point solution to the matroid polytope intersected with at most m linear constraints has a support of size most k + (see also Lau et al. (201)) Chap. 11).
4

---

Under review as a conference paper at ICLR 2023
Algorithm 1: Iterative Rounding
Input: A = Ai U...U Am, F, kt d, X
2 Output: A set of centers of size at most & + m..
3 Solve LP1 to get optimal solution (x", "","""" =-) and reate set F by splitting facilities.
4 Set F; = [j E F > 03. D; = max : 2 > 0) each E U4.
5 Sort clients in increasing order of D, and greedily include clients in L/" while maintaining that
{F] : i E U'") remain disjoint.
Set = A A'"
7 while there is some tight constraint from Eq.
5 do
8
if there exists U such that y (B)) (i.e. Eq. 8 tight for i) then
F; <- B,, - P. B. Li F. d(i, 1) 1 =x): and Update-24"
Find an extreme point solution y the linear program LPU"" D). return the support of y in the solution of LP('", ,4' D)
Procedure Update-UL Ut (i)
2 for every i' E U2 that Fn + 0. Dy > Dj then
3. Remove all i' that represent from 2t and add them to 24. u' + 21 U (i).
4
We now formalize the argument and specify how one iteratively groups the clients. We iteratively remove/change constraints in LP2 as we do the grouping while ensuring that linear program's 's cost does not increase. We initialize D. max(dl(i j) Fig 0} max
[d(i.) max(d(i,) j) j E F.) for each client i. We maintain a set of representative clients Ut" We say a client E lt represents a client i' if they share a facility, i.e., P. n F. * 0. and D; Dr. The representative clients do not share any facility with each other. The non-representative clients are put in the set Ut, We initialize Ut as follows. Sort clients in increasing order of D:. Greedily add clients to Lt* while maintaining F; n Fr = 0 for all i + i' E Lt". Observe that 41 is maximal with above property, i.e., for every & U", there is E Ut such that Fi Fe + and D. S Dr. We will maintain this invariant the algorithm. For clients i E U2 we set B, to be the facilities in F; that are within distance of 14X In each iteration we solve the following linear program and update U", U D, 's, B ss and Ft's.
min 2
(LPUU D))
s.t. 2 Eier,ru wi(s) Ejer, d(i,j)
+ ELEANN wi(s) (ESe,, d(i.j)'s, + +11 ((B))(D)) v1 sssm. m.
(5)
ΣjEド Vj =k,
(6)
ΣjER. SEP.Vj=1! =1 EV'
(7)
EjEB Bj Uj ViEUs 0.
(8)
(9)
For clients in E 2t, we only insist that we pick at most one facility from B, (see Eq. 8 The objective modified to pay D; for any fractional shortfall of facilities in this smaller ball (see Eq. 5). Observe that if this additional constraint Eq. 8 becomes tight for some j E 2t, we can decrease D, by factor of (1 X) for this client and then update 21" accordingly to see if can be included in it. Also, we round each d(i.j) j) to the nearest power of (1 + A). This only changes the objective by a factor of (1 + A) and we abuse notation assume that d satisfies this constraint (it might no longer be a metric but in the final assignment, we will work with its metric completion). The iterative algorithm runs as described in Algorithm [ It is possible that a client moves between u' and tt* but any time that point is processed in u (Step 3(a) above), D; is divided by (1 + A).
Thus the algorithm takes On log (diam) iterations. where diam is the distance between the two farthest points. Finally the result is implied by the following claims (proved in the appendix).
Claim 2.2. The cost of the L.P is non-increasing over iterations. Moreover, when the algorithm ends, there are at most lo + m facilities in the support.
5

---

Under review as a conference paper at ICLR 2023
Algorithm 2: Sparsify
Input: A = Ai U...U Am,FF k E
2 Output: A set of fair k-median instances.
for = 1,...., m²t and t' facility pairs (f, Hi. (ee.de) do
Output I (F',A,,, k. d), where F = FV Up-1 (eALL()r,d(rr33
4
Claim 2.3. For any client i' E W there is always one total facility at a distance of at most (1 + 2(1 + X)/A) De, Le.. Ezdl 2)00220-M//DD yj 2
Claim 2.4. Lel ÿ be an integral solution to linear program LP(U" ,2,,, D) after the last itera- lion. Then, there is solution (i, 5) to the linear program LPI such that objective is at most ((1+2(1 + A)/X)L+A])* times the objective of the linear program LP("" ,u DD)
Now we prove Theorem by substituting the best À in Lemma 2.1
Proof of Theorem 1.7 By Lemma the output vector of Algorithm corresponding to the centers has a support of size at most k + m. Rounding up all the fractional centers, we get a solution with at most + m centers and a cost
most (1++2(1 + (1+A)(++))) of the optimal. We optimize over A by taking the gradient of (1+2(1 + X) A) and setting it to zero. This gives the optimum value of À 2/33. Substituting this, gives total approximation factor of (5 2/6)".
3 APPROXIMATION ALGORITHMS FOR FAIR k CLUSTERING
We first show how to generate set of instances such that at least one of them is sparse and has the same optimal objective value as the original instance. Then we present our algorithm to find a solution with & facilities from seeudo-solution with k + facilities for sparse instance, inspired by Li and Svensson (0166). We need to address new difficulties: the sparsity with respect to all groups 5 E [m]; and our pseudo-solution has additional centers (instead of O(1) additional centers), we need a sparser instance compared to Li and Svensson (2016). One new technique is solving the optimization problem given in Step 1I of Algorithm 3 (Lemma 4.1). This is trivial for the vanilla k-median but in the fair setting, we use certain properties of the extreme points of intersection of matroid polytope with half-spaces, and combine this with careful enumeration.
For an instance I, we denote the cost of a set of facilities by costi (F). For point and r >> 0, denote the facilities in the ball of radius at q by FBallz(g, r). This does not contain facilities at distance exactly from For group E [m]. the set of clients of s in the ball of radius r at q is CBa #Ballz,s(0 (g, r). Note that because we consider the clients weights on points, CBall1,, is actually a set of (point, weight) pairs. We let CBallz,sle
ElecBalLZ. (,(1).
Definition 3.1. [Sparse Instance] For O, an instance of the fair l, clustering problem I (K,F,, A, d) is a-sparse for each fucility E F and group E [m].
(gdli, OPT2))* |CBallz,,(j 3/2 d(j, OPT2))l S a.
We say that a facility j a-dense if violates the above for some group s E [m]]
To motivate the definition, let I be an a-sparse instance, OPTz be an optimal solution of I. be facility not OPT, and j* be the closest facility in OPT, to j. Let F a solution that contains and a be the total cost of the clients of group E [m]] that are connected to in solution F. Then,
(cost of group s for solution PUJ (i*) < (cost of group for solution F) + ((p). (a + 15.))
This property implics that if a < optz/m, then replacing m different facilities can increase the cost by a factor of (p)) plus 20(p). -ppt,, and the integrality gap of the LP relaxation 20(p), The next algorithm generates set of instances such that at least one of them has objective value equal to optz and is (optz//mt)-spp
for a fixed integer t.
Lemma 3.2. Algorithm 2 runs in ((m2t) time and produces instances of the socially fair lp clus- tering problem such that at least one of them satisfies the following: (1) The optimal value of the original instance I is equal to the optimal value of the produced instance I'; (2) I' is optx sparse. mt
6

---

Under review as a conference paper at ICLR 2023
4 CONVERTING A SOLUTION WITH k + m CENTERS TO ONE WITH t CENTERS
We first analyze the special case when the set of facilities is partitioned to ls disjoint sets and we are constrained pick exactly one from each set. This will be subroutine in our algorithm.
Lemma 4.1. Let , Sk be disjoint sets such that S1 U...U Sse [n]. For g [m]. j E [A.].
v E Sz. let ag (n-5) 2 0. Then there is an (nk) ( 2 -tme algorithm that finds a (aproxiiee solution to mille maxge[m] Eje(s] Oeey
(g.))
Proof. The LP relaxation of the above problem is
min A such that ΣjE( Eves,
0g xe 0, Vg E [m].
(9J) (
Eves, Io = 1, Vj E [k] x(5) 2 O, Vj E [k]
Note that this is equivalent to optimizing over partition matroid with extra linear constraints. Therefore by Lemma [.3 an extreme point solution has a support of size at most k + m. Now suppose 0* is the optimal integral objective value, and of E St,..., oi Sy are the points that (g.f) achieve this optimal objective. For each E [m], at most m/c c many a , E [be], can be more
Oz) I 0" Suppose, for each g E [m], we guess the set of indices than -0 because ΣjE(H) (a.)
2 m =0)). This takes RO(mm/e) time by enumerating over set [A:]. Let T = Ti A...UUUT ..... F E T, we also guess 1z in the optimum solution by enumerating over Sy's, ss
T, {j [k]
(9.)
o5
j E T. This increases the running time by multiplicative factor of n (emm/e) since vy E S, and |S,| S n. Based on these guesses, we can set the corresponding variables in the LP, i.e., for each S such that j E T, we add the following constraints for Sj. x if uz. and x! 0, otherwise. The number of LPs generated by this enumeration is (nk) ((m²/<)
We solve all such LPs to get optimum extreme points. Let (8, x(1) point for the LP corresponding to the right guess (i.e., the guess in which we have identified all indices j E [k:] along with their corresponding 2z such that there exists g E [m]] where 007
x ((()) be an optimum extreme
(9.5) Z
m. -),)) Therefore δ 5=0 0". Let R- ii E [k] I & {0, {0, 131S J. Since the feasible region of the LP corresponds to the intersection of a matroid polytope and m half-spaces, by Lemma 1.3 the size of the support of an extreme solution is k + m. Moreover any cluster with E [k] that have fractional centers in the extreme point solution, contributes at least 2 to the size of the support because of the equality constraint in the LP. Therefore R| (k- [R] I k + which implies |R| < m.
Now we guess the og for all j E R. By construction, RnT = 0. Therefore for all E R and g E [m].
a (a-)) < m -000. Therefore for all E [m]] ΣjeR vr
(gو) < m 0 e Thus for the right guess
of o3. j E R, we get an integral solution with a cost less than or equal to 0 + e0 < (1 + +e L
Algorithm 3 is our main procedure to convert a solution with k + m centers to a solution with centers. We need 33 to be in the interval mentioned in Lemma 4.2 To achieve this we guess optr as different powers of two and try the corresponding 3's. The main idea behind the algorithm is that in a pscudo-solution of sparse instance, there are only a few (< m²²) facilities that are far from facilities in the optimal solution. So the algorithm tries to guess those facilities and replace them by facilities in the optimal solution. For the rest of the facilities in the pseudo-solution (which are close to facilities in the optimal solution), the algorithm solves an optimization problem (Lemma to find a set of facilities with cost comparable to the optimal solution.
Finally combining the following lemma (proved in the appendix) with Lemma 3.2 (spasiffication and Theorem 1.I (bicriteria algorithm) implies Theorem 1.2
Lemma 4.2. LetI (k., F, A, d) be an mt -sparse instance of the (Lp, cclusterin problem. T be a pseudo-solution with most k + m centers, é' 0, 5 min log(1+e') }), 2 4(1 3)
optz
12
7

---

Under review as a conference paper at ICLR 2023
Algorithm 3: Obtaining solution from a pseudo-solution
Input: Instance I, 9, pseudo- souudo-olluton T. <'>00, óe (0, min(s log()=+1))) and integer 12 424-
2 Output: A solution with at most & centers.
3 T' <-
while [T'] k and there is j T' costz(T" (31) + +
5 if [T'] S k then return T":
forall 2> S and V _ such that [D] + VI and (V < m²t do
7
For j E D, set L, = d(j (i})
For E I,
4/3 10.0
E
min [n(( .((i, v)
iecBaLIZ. (33333
Let (fr : :
JED FBa [ajall(jj,00 )L,} be (1 + +e) approxximtt solution to (see Lemma 4.1
min BED
max sE(m JED
Σ
(ad')
v
return S arg migminss (Sst)(Sp.v)
be an integer. and 2. (optz + (1+ costr((T) <B3 2 (2optz + (1+ c)
mi
Then Algorithm finds set S E F in time n m² ((p) such that |S| I k and costz(S) < (0(1) (1 +1+e7 e)) (costz(T) + optz).
EMPIRICAL STUDY
We compare our algorithm with previously best algorithms in the literature benchmark datasets for socially fair k-median problem. Namely, we compare our bicriteria algorithm with AAbasi et al. (202T) (ABV), and our exact algorithm (that outputs exactly is centers) with Makarychev and Vakil- ian (2021) (MV). Since our bicriteria algorithm produces only small number of extra centers (e.g.. for two groups, our algorithm only produces one extra center see Section E.3 we search over the best k-subset in the set of k + m selected centers. However, instead of performing an exhaustive linear programming solver to find the best k-subset. Our code is written in MATLAB. We use IBM ILOG CPLEX 12.10 to solve the linear programs (and mixed-integer programs). We used a MacBook Pro (2019) with a 2.3 GHz 8-Core Intel Core i9 processor, 16 GB 2667 MHz DDR4 memory card, a Intel UHD Graphics 630 1536 MB graphic card, TB of SSD storage, and macOS version 1
search combinatorially, we use
Datasets. We use three benchmark datasets that have been extensively used in the fairness litera- ture. Similar to other works in fair clustering Chierichetti et al. (017). , we subsample the points in the datasets. Namely, the used datasets is in the following. (1) Credit dataset Ych and Lien (2009) consists of records of 30000 individuals with 21 features. We divided the multi-categorical education attribute two de- mographic groups: "higher educated" and "lower educated." (2) Adult dataset Kohavi et al. (196);; Asuncion and Newman (2007) contains records of 48842 individuals collected from census data, with 103 features. We consider five racial groups of "Amer-Indian--skiin "Black", "White", and "Other" for one of our experiments. For another experiment we consider the intersectional groups of race and gender (male and female) that results in 10 groups (3) COMPAS dataset Angwin al.) (2016) gathered by ProPublica and contains the recidivism rates for 9898 defendants. The data is divided to two racial groups of African-Americal (AA) and Caucasians (C). The results for the COMPAS datasets are included in the appendix.
consider the first 500 examples in each dataset. A quick overview of
"AsianPac-Islande"
Bicriteria approximation. The ABV algorithm, first solves the natural LP relaxation and then uses the "filtering" technique and Vitter (1992); ) Charikar et al. (0022 to round the fractional solution 1, the algorithm outputs at most k/(1 e) centers
to integral one. Given a parameter 0 and guarantees 2/c approximation. In our comparison, we consider that gives almost the same algorithm. Tables in Section E.3 summarise the number of selected centers
number of centers for different and e. The À parameter in our algorithm (see Algorithm [and Lemma 2.1) determines the factor of decrease in the radii of client balls in the iterative rounding algorithm. As illustrated in
8

---

Under review as a conference paper at ICLR 2023
Our Hirsi 14
16
Bieri
Our Hari,
-BVV Bieri. 0.2
ARV Bleri.
14
ARV Bies.
3.5
ABV Bieri. -. 0.5
ABV Bieri 0.4
ABV Bies - 0.4
12
8
10
30
40
10
50
(a) Credit dataset (2 groups).
(b) Adult dataset (5 groups).
(c) Adult dataset (10 groups).
Figure 2: Comparison of our bicriteria algorithm with ABV Abbasi et al. (202I). The number of centers algorithm selects is close to k and is often smaller than ABV (see Section E.3)
Section E.2, the performance of our algorithm do not change significantly by changing A. So in our comparisons, fix À 0.6. Figure 4 illustrates that our algorithm outperforms ABV on different benchmark datasets. The gap between the performance of our algorithm and ABV becomes larger as the number of groups and & become larger. For example, for the Adult dataset with 10 groups and k = 50, the objective value of ABV is almost twice of the objective that our algorithm achieves.
Exactly centers. The MV algorithm, fist sparsifies the linear programming relaxation by setting the connection variables of points that are far from each other to zero It then adopts a randomized rounding algorithm similar to Charikar et al. (2002) based on consolidating centers and points. In the process of rounding, it produces a (1 reesttiieee solution which is a solution where each center is either open by a fraction of at least (1 11-7) 7) or is zero. The algorithm needs y < 0.5. The results of MV for different values of y are presented in Section F.2 It appears that MV performs better for larger values of 7, so below we use 7 = 0.1 and 7 0.4 for our comparisons. Figure 5 illustrates that our algorithms outperforms MV different benchmark datasets. Similar to the bicriteria case, the gap between the performance of our algorithm and MV becomes larger as the number of groups and & become larger. For example, for the Adult dataset with 5 or 10 groups and k 50, the objective value of MV is almost thrice of the objective that our algorithm achieves.
50
Our Exact A- 0.5
Our Exaet- A-10 0.5
Our Exact 0.6
MV Exnct- 0.1 MV Exact-
JV Exnctt 0.1
MV Exoct- 0.4
40
MV Exact y U.l
MV Exact
30
3-
16
2.5
10
10
2
10
30
40
50
10
20
50
20
90
40
(a) Credit datasct (2 groups).
(b) Adult datasct (5 groups)
(c) Adult dataset (10 groups).
Figure 3: Comparison of our algorithm with ls centers with MV Makarychev and Vakilian 2021
Empirical running time. We compare the running time of our algorithms with that of ABV and MV on the three datasets (see Section [.44) To summarize, the running times of our bicriteria algorithm and the exact algorithm with exhaustive search are virtually the same when the number of groups is no more than 5. Moreover our algorithmss' times are comparable to ABV and are significantly less than MV in most cases. The latter is because MV needs to guess the value of the optimal objective value. Therefore it needs to run the algorithm multiple times. We run the algorithm with 5 different values (by multiplying different factors of two) and output the best out of these for MV.
CONCLUSION
We presented a polynomial time bicrteria algorithm for the socially fair (L,, k) clluutrrni with m groups that outputs at most & + centers. Using this, we presented two different constant-factor approximation algorithms that return exactly i centers. An interesting future work is to investigate the use of recently introduced techniques in k-means++ Lattanzi and Sohler (201);; Choo et al. (2020) forw faster constant-facte factor approximation algorithms for socially fair k-mann. It is also interesting to explore scalable algorithms, for example, using the coreset framework.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Abbasi, M., Bhaskara, A., and Venkatasubrammnnian, S. (2021). Fair clustering via equitable group representations. ACM FAceT.
Abraham, S. S., Sundaram, S. S., et al. (2020). Fairness in clustering with multiple sensitive at- tributes. International Conference on Extending Database Technology.
Ahmadian, S., Epasto, A., Kumar, R., and Mahdian, M. (2019). Clustering without over- representation. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 267-275
Anegg, G., Angelidakis, H., Kurpisz, A., and Zenklusen, R. (2021). A technique for obtaining true approximations for k-center with covering constraints. Mathematical Programming, pages 1-25.
Angwin, J., Larson, J., Mattu, S., and Kirchner, L. (2016). Machine bias. In Ethics of Data and Analytics, pages 2542664. Auerbach Publications.
Anthony, B. M., Goyal, V., Gupta, A., and Nagarajan, V. (2010). A plant location guide for the unsure: Approximation algorithms for min-max location problems. Math. Oper. Res., 35(1):79- 101.
Asuncion, A. and Newman, D. (2007). Uci machine learning repository.
Benthall, S. and Haynes, B. D. (2019). Racial categories in machine learning. In Proceedings of the conference on fairness, accountability, and transparency, pages 289-298.
Bera, S., Chakrabarty, D., Flores, N., and Negahbani, M. (2019). Fair algorithms for clustering. Advances in Neural Information Processing Systems, 32.
Bhattacharya, S., Chalermsook, P., Mehlhorn, K., and Neumann, A. (2014). New approximability results for the robust k- k-median problem. In Algorithm Theory SWAT.
Brubach, B., Chakrabarti, D., Dickerson, J., Khuller, S., Srinivasan, A., and Tsepenekas, L. (2020). A pairwise fair and community-preserviiii approach to k-center clustering. In International Con- ference on Machine Learning, pages 1178-1189. PMLR.
Byrka, J., Pensyl, T., Rybicki, B.. Srinivasan, A., and Trinh, K. (2014). An improved approximation for k-median, and positive correlation in budgeted optimization. In Proceedings of the swenty- sixth annual ACM-SIAM symposium Discrete algorithms, pages 737-756. SIAM.
Chakrabarti, D., Dickerson, J. P., Esmacili, S. A., Srinivasan, A., and Tsepenekas, L. (2022). A notion of individually fair clustering: a-equitable k-center. In International Conference on Artificial Intelligence and Statistics, pages 6387-6408. PMLR.
Charikar, M., Guha, S., Tardos, é.,, and Shmoys, B. (2002). A constant-factor approximation algorithm for the k-median problem. Journal of Computer and System Sciences, 65(1):129-149)
Chen, X., Fain, B., Lyu, I.., and Munagala, K. (2019). Proportionally fair clustering. International Conference on Machine Learning, pages 1032-1041. PMLR.
Chierichetti, F., Kumar, R., Lattanzi. S., and Vassilvitskii, S. (2017). Fair clustering through fairlets. Advances in Neural Information Processing Systems, 30.
Choo, D., Grunau, C., Portmann, J., and Rozhon, V. (2020). k-means+4: few more steps yield constant approximation. In International Conference on Machine Learning, pages 1909-1917. PMLR.
Drineas, P., Frieze, A., Kannan, R., Vempala, S., and Vinay, V. (2004). Clustering large graphs via the singular value decomposition. Machine learning, 56(1):9-33.
Dwork, C., Hardt, M., Pitassi, T., Reingold, O., and Zemel, R. (2012). Fairness through awareness. In Proceedings of the 3rd innovations in theoretical computer science conference, pages 214-226.
10

---

Under review as a conference paper at ICLR 2023
Ghadiri, M., Samadi, S., and Vempala, S. S. (2021). Socially fair k-means clustering. In ACM FAccT.
Gorwa, R., Binns, R., and Katzenbach, C. (2020). Algorithmic content moderation: Techni- cal and political challenges in the automation of platform governance. Big Data & Society, 7()):0039517719897999
Goyal, D. and Jaiswal, R. (2021). FPT approximation for socially fair clustering. arXiv preprint (rXiv:2/06.06755
Grandoni, F., Ravi, R., Singh, M., and Zenklusen, R. (2014). New approaches multi-objective optimization. Mathematical Programming, 146(1):525-555
Guha, S. and Khuller, S. (1999.. Greedy strikes back: Improved facility location algorithms. Journal of algorithms, 31(1):228-245
Gupta, A., Moseley, B., and Zhou, R. (2021). Structural iterative rounding for generalized k-median problems. In ICALP.
Gupta, S., Jalan, A., Ranade, G., Yang, H., and Zhuang, S. (2020). Too many fairness metrics: Is there solution? Available at SSRN 3554829.
Hajiaghayi, M.. Khandekar, R., and Kortsarz, G. (2010). Budgeted red-blue median and its general- izations. In European Symposium Algorithms, pages 314-325, Springer.
Hutchinson, B. and Mitchell, M. (2019). 50 years of test (un) faimess: Lessons for machine learning. In Proceedings of the Conference on Fairness, Accountability: and Transparency, pages 49-58.
Jia, X., Sheth, K., and Svensson, O. (2021). Fair colorful k-center clustering. Mathematical Pro- gramming, pages 1-22.
Jung, C., Kannan, S., and Lutz, N. (2020). A center in your neighborhood: Fairness in facility location. Proceedings of the Symposium Foundations of Responsible Computing.
Kanungo, T., Mount, D. M., Netanyahu, N. S., Piatko, C. D., Silverman, R., and Wu, A. Y. (2004). A local search approximation algorithm for k-means clustering. Computational Geometry, 28(2- 31:89-112.
Kearns, M. and Roth, A. (2019). The ethical algorithm: The science of socially aware algorithm design. Oxford University Press.
Kleindessner, M., Awasthi, P., and Morgenstem, J. (2019). Fair k-center clustering for data summa- rization. In International Conference on Machine Learning, pages 3448-3457. PMLR.
Kleindessner, M., Awasthi, P., and Morgenstem, (2020). A notion individual fairness for clustering. arXiv preprint 200i:200000049600
Kohavi, R. et al. (1996). Scaling up the accuracy of naive-bayes classifiers: A decision-tree hybrid. In Kdd, volume 96, pages 202-207.
Krishnaswamy, R., Kumar, A., Nagarajan, V., Sabharwal, Y., and Saha, B. (2011). The matroid median problem. In Proceedings of the twent--second annual annual ACM-SIAM symposium Discrete Algorithms, pages 1117-1130. SIAM.
Krishnaswamy, R., Li, S., and Sandeep, S. (2018). Constant approximation for k-median and k- means with outliers via iterative rounding. STOC 2018.
Lattanzi, S. and Sohler, C. (2019). A better k-means++ algorithm via local search. In International Conference Machine Learning, pages 3662-3671. PMLR.
Lau. L. C., Ravi, R., and Singh, M. (2011). Iterative methods in combinatorial optimization, vol- ume 46. Cambridge University Press.
Li, S. and Svensson, O. (2016). Approximating k-median via pscudo-approximation SIAM Journal Computing, 5542).500-547.
11

---

Under review as a conference paper at ICLR 2023
Lin, J.-H. and Vitter, J. S. (1992). Approximation algorithms for geometric median problems. In- formation Processing Letters, 44(5):245-2 -49.
Mahabadi, S. and Vakilian, A. (2020). Individual fairness for k-clustering, In International Confer- ence on Machine Learning, pages 6586-6596. PMLR.
Makarychev, Y. and Vakilian, A. (2021). Approximation algorithms for socially fair clustering. In COLT. PMLR.
Micha, E. and Shah, N. (2020). Proportionally fair clustering revisited. In 47th International Col- loquium on Automata, Languages, and Programming (ICALP 2020). Schloss Leibbii-- Zentrum für Informatik.
Samadi, S., Tantipongpipat, U., Morgenstern, H., Singh, M., and Vempala, S. (2018). The price of fair pea: One extra dimension. Advances in neural information processing systems, 31.
Schrijver, A. (2003). Combinatorial optimization: polyhedra and efficiency, volume 24. Springer Science Business Media.
Tantipongpipat, U. Samadi, S., Singh, M., Morgenstern, J. H., and Vempala, S. (2019). Multi- criteria dimensionality reduction with applications to fairness. Advances in neural information processing systems, 32.
Vakilian, A. and Yalciner, M. (2022). Improved approximation algorithms for individually fair clustering. In International Conference on Artificial Intelligence and Statistics, pages 8758-8779. PMLR.
Yeh, I-C. and Lien, C.-h. (2009). The comparisons of data mining techniques for the predic- tive accuracy of probability of default of credit card clients. Expert systems with applications, 36(2):2473-280..
12

---

Under review as a conference paper at ICLR 2023
A EXHAUSTIVE SEARCH
Lemma A.1 (Goyal and Jaiswal 2021 Let k' > k and S be a set of centers of size k' and cost C for the socially fair (cp: ki-clutteinng problem with groups. Let T C S be set of size i with minimum cost among all subsets of size is of S. Then the cost of T is less than or equal to 30-1(C 2opt) where opt is the cost of the optimal solution.
Proof. Let OPT be an optimal set of centers. For each center OPT, let so be the closest center in S to o, i.c., So = arg min d(s, o). Let T" == {so O OPT}. Because the size of OPT T is k, [T') S k. We show that the cost of T" less than or equal to 3 + 2opt). The result follows from this because 7" C S and [T"] S k.
Let be a client and o; be the closest facility in OPT to i. Let 1/ be the closest facility to o, in
T which means & is also the closest facility to in S. Moreover let be the closest facility to in S. By triangle incquality, d(i, (2) S d(i, o;) )
+ d(o,,tt). By definition of t. d(o,, &)) S
d(o,, s:). Therefore ()) I o() d(o,, Moreover by triangle inequality d(o,,s) S
d(i, 0;) + d(i, 8;). Therefore d(i,t) ()) _ od) + d(i,s;). Taking both sides to the power of
p and using the power mean inequality, ie., (x + y + 2) < 3x" + y" 2²), we conclude
d(i, t1)² 1 3p- (2d(i, o,) + d(i,, s, s)). The result follows from summing such inequality for each group and taking the maximum over groups.
B OMITTED PROOFS OF SECTION 2
Proof of Claim 2.2 In each iteration, put at most client in Ut. For this client, Eq. is tight, ie.. EjeB, 8/ Note that we update F; to B,. Therefore the new point in lt* satisfics Eq. 7 Moreover, for a point i' that is removed from Ut, we have
JEB,
JEF.
Therefore such a point satisfies Eq. g Hence feasible solution to the LP of iteration t is also feasible for iteration t + 1. Therefore the cost of the LP is non -on-increasing over iterations.
The second statement follows since if no constraint from Eq. g is tight, then the linear program is the intersection of a matroid polytope with m linear constraints and the result follows from Lemma
Proof of Claim 2.3 Let t be the iteration where Dp is updated for the last time. If Dy is only set once at Line 4 of Algorithm | and it is never updated, then t = 0. We first show that immediately distance of at most 3D, from V. If = O, then there existed E 24" such that F, n Fvr + 0 and D; I Dr. Therefore by triangle inequality, all the facilities in F; are within distance of at most 3Dy from i', see Figure [ (a). Hence because Eq, 7 enforces one total facility in F,, there exists one total facility at a distance of at most 3D, from a. If > 0, then i' is moved from 4t* 2 because iteration t, facility is added to Lt* such that D, < Dy and F. n F.. # 0 - see the condition of Procedure Update-l(" (i) in Algorithm [ Again because of enforcement of Eq. and triangle inequality, there exists one total facility at a distance of at most 3D from i' immediately after iteration f.
after iteration f, there is total facility
Now note that after iteration f, the facility E Lt" with F.FF, o and D, S D3. might get removed
from Ut. In which case, we do not have the guarantee of Eq. 7 anny longer. Let in : i. We define ipt1 to be the client that has caused the removal of client ip (through Procedure Update-((*(i)) from l* after iteration l. Note that by the condition of Update-((*(i)) (1)) from Ut, Dep < D Dap
Therefore because we have rounded the distances to multiples of (1 + A), we have Di S Dip
Let i, be the last point in this chain, i.e., i, has caused the removal of i and i, has stayed in UI until termination of the algorithm. Then by guarantee of Eq. 7 and triangle inequality, there is one total facility for i' within a distance of
D2
1+ 2(1 111+(+11)) Dr.
D3 + Σ 2D, S Dr +2
Σ 1=0
<
(1 + A>i
1=
13

---

Under review as a conference paper at ICLR 2023
By Claim 2.2 at every iteration, the cost of the linear program only decreases since a feasible solution to previous iteration remains feasible for the next iteration. Thus the ob- jective value of ÿ in LP(," 2t, D) is at most (1 + 2)" the optimal cost of LP1 (where we lost the factor of (1 + X) by rounding all distances to powers of (1 + A)).
Proof of Claim 2.4
We construct such that (ś, ū) is feasible LP1. First note that the above procedure always terminates. We construct & by processing clients one by one. We process the clients in 4 and U as follows. For any i 21", we define &új = ÚJ for each j F,. Observe that have Ejer, Zijj for such i Ut" and we obtain feasibility for this client. For any E U' we define Big = 3) for each j B₁. Observe that we only insisted EjEB, D3 S and therefore we still need to find -jen, Lig = Eien, ÚJ facilities to assign to client i. For this remaining amount 1 - (B,), we notice by Claim 2.3, there is at least one facility within distance (1+ )0+ D, of this client. Thus we can assign the remaining (B.) facility to client i at a distance of no more
than (1 2(1)))) D:. Note that the cost is only increased by a factor of (1 2(14-2)
C OMITTED PROOFS OF SECTION 3
Proof of Lemma
3.2 First note that facility i in OPT, cannot be a-dense because d(ii, OP OPTx)) = 0.
Let (j1,J),....
(ee be sequence of pairs of facilities such that for every b = 1,.....,
jo E
an optx dense facility; and ml
j/ is the closest facility to jo in OPTz.
We show that S m²t. For b E [ and 8 E [m], let B == CBall lBBalla (Jo (d).,,))). First show that for any group E im]. the client balls BL...... Be. are disjoint. Let 1 I w < l. By triangle inequality d(jw.Ja) S d(jwrJz) + d(je, Moreover by definition jw & FBallr(js: J1)) Thus d(ja.1)) S J(jm: Hence d(w..'' S 2d(jur]z). Since in is the closest facility to ju in OPTT, d(ww Tw) I d(jurJ'). Therefore d(ju:Ke) Combining this with J(jz.1)) I d(fw::z) implies 1 (d((e. + d(jw.Ju S d(jz.Jw). If B... and Bu., overlap then there exists u B,, DB and by triangle inequality, J() S d(js, u) d(jw.u) < d'.... + jd Jw), which is a contradiction.
it) S 2d((wwnIs).
Therefore for [m]] Br.j...,, Bt, are disjoint. Also since AI...., A, are disjoint, all of B
are disjoint for b E [e] and E [m]. By definition, for any b E [é]. there exists st E [m]] such that (2d(js, OPTz)) BB optr moptz. Thus
Therefore, if f > m²,, Eb= (fd()),OPTZ)) BB >
mt
Σ (2 |Br. b=1
2 Σ Σ ( ((U))OOTT)) |Bo.ol > moptz. SE xE(m) b=1
8
max sE(m)
Note that the connection cost of a client in By,s the optimal solution is at least (gd(ís, opTz)) = K))) Therefore, as the B,,'s are disjoint, optz Z max.g(ml Ei (2d(js, OPTx))" BB.s This is a contradiction. Therefore l S m²t. Thus Al- gorithm 2 returns an instance with the desired properties.
D OMITTED PROOFS OF SECTION 4
Proof of Lemma 4.2 If Algorithm 3 ends in Step 7, then costr(T) + m3 is at most costz(T) + ? (2optz + (1 + (ccost(T)) = O (optz + costz(T)). Otherwise, we run the loop. Now
we show that there exist sets D, C T' and Vo C F such that Pnl < m²t, [Dal + Vol = k
and So,.vo satisfies the desired properties. For facility E T', let L, d(j, T (i)) and
14

---

Under review as a conference paper at ICLR 2023
L OPTT)) We say j I is determined if lj I 8L,, Otherwise, say j is undetermined. Let Do = [j E T Ej & òLا}. For j E Du, let fj be the closest facility to j in OPTz- Let Vo- = OPTI \ {fī : :j E Do}- First note that for any two distinct facilities in j. E Do- d(j.j") 2 max(Ly, Ly). Moreover by definition, d(j.fj) S òL, S 5 m L.r3. Therefore by triangle inequality, dfj', 2 (1 - 5) max [Tyg }. Moreover by definition and because 8 E (0, g). (1 (1-00) 6) maxx(L) (Lj, Ly,, > 8Ly 2 d(j', dff', Therefore d(j', > d'j', Thus for any two distinct j.j' E Do. fj # fj.
Therefore KJ} j E DoHl = [Pol. Thus Vol = |PPTT| 1Dol = k Pol. Let Uo T \ Do be the set of undetermined facilities. Since |T| > k. Vol k [Pol
| Ho1 < Uo]- We show [24g] < m²t. For every j E T' and s E [m]. let As, be the set of clients of group s that connected to j in solution T and let C..y be the total connection cost of these clients. Therefore
k =
costx(T) maxxe[m] EJET Ca.. Let j = arg minjeu, ExE(m) Caj. Let j be the clos- est facility to j in T' (j"). i.e., d(j", ,j) = Ly:. Then costz(T' ((7)) costx(T) S max EiEA,.- d(i.j)p. For [m], let A
A.j n CBallr,,(i', (ōLj.) and Any = As.- \ A..-. By triangle inequality, for any i E A d(i,)) J) S (1 + {8)
Moreover since j' is undetermined, d(i.j) < (1 f0) = ( + }) < Zeg, and for any E [m], CBallz,,()", 38L,.) S CBallz,a0"" ). Thus Eieay d(i,j)
( ) ICBallz, (6.)) Therefore since I is setz-sparse sparse instance, Eiery j)i S
mt
mn optz, For i E Any. d(i,j") 2 joLz. Thus jd(i, 2 Lgg and by triangle inequality,
d(i,)) S d(i,j") + d(j", = d(i,j") + Lg S (1 j*), Therefore
optI mt
3 + (1 yCoss)
costr(T \ ((-) costz(T) S max sE(m]
8
optz mt
+ (1 + 3 )) Ees(m) Ca.e.
(10)
By definition, Exe(m) Cz.j" minjeuo Exeim) Oaj S
mcostr(T)) 1u
So if (M 2 m²t, then
Eee(m) Ca.j' S (T') ml
Moreover, since IT \ T <,,
costx(T)) costr(T) + m3 S costz(T)+ 2 t
3 20ptz + (1+ Pcosst(T))
opt 2 (Costz(T).
1+ 3
Combining with Eq. 10 costz (T\(')) cost) < 2 2 + +1+ 3 cost
mnt < B. This
is a contradiction because jL should be removed in Step 4 of Algorithm 3 Therefore [44 < m²t.
Now, we need to bound the cost of Sp For E Do and E [mm, let CBallz,, (j. 1 L;). By triangle inequality the distance of to any facility in FBallz(j &L,) is at most ( - 8) For a facility j' E Do. j' * j. by triangle inequality and because d(j.j') 2 Lyr the distance of i to any facility in FBall. ((', 8Ly)) ) is at least
d(i-j") - 3
- - 2 d(j.j") -
3 8)L, -
2
3 + < 3 - 8. Therefore, i is either connected to fj or to a facility in Vo. Let " (e.f)'s be as defined in Algorithm for Do and Vo. Let (T, j E Do) ae (1 + --p-prpoxiimtte so- lution for the following, obtained by Lemma 4.1 For E [m]] let T. USED. CBallz, Lz)3). Since for Do. f7 OPT''s 's are also in balls (Balll(j,8T,
For 5 < J. we have
max.5|ml [m)] Eier, d(i,SDo.v)) < (1 + max.e(m) Eier, d(i,oPTz)'
Now consider a client é E A, \ T.. If in the optimal solution, is connected to a facility in Vn- then by definition, d(i, OPTz) 2 d(i, (...).).).. Otherwise, in the optimal solution, is connected
15

---

Under review as a conference paper at ICLR 2023
fj FBallz(i,8L,) for some E Do- We compare fti to d(i,f))
Since fJ (
FBa)1r() by triangle inequality and because d(i.j) 3
S
(d())))
(L,13+6L,) 1+38
Thus because 8 <
1+38 8 1-33
< 1 + 128. Moreover since log(1+e')
(2,/3-dL,)²
1-36
12
costz(SDo.W vo) I +1+C E optz. Finally note that the loop runs for n O(m2t) iterations because
|V| < m²i and IT \ D S m²t + m. Moreover by Lemma 4.1 each iteration runs in (nk) /c)
time.
16

---

Under review as a conference paper at ICLR 2023
E OMITTED EMPIRICAL RESULTS
E. COMPARISON OF ALGORITHMS SHOWING BOTH MAXIMUM AND MINIMUM
Our Rei 08 (light Bd3
Our Bkoi
14
Our Reci 06 tman:
Our Ren 08 Bower EL
Ove Ren 0. lntd
ABV (oue
4BV
ABV Den (0) ABV Ban ---9 (AAA)
ABV Blas 0.5 HRiae Bd)
ABV Btei (snsc)
4BV Biss LLowe E
ABV Biest (ans))
2
(a) Credit Dataset (2 groups).
(b) COMPAS dataset (2 groups).
(c) Adult dataset (5 groups).
Figure 4: Comparison of our bicriteria algorithm with ABV Abbasi et al. (2021). The max and min
on Subfigure (c) across the demographic groups and are used to prevent cluttering plots with groups. The number of centers our algorithm selects is close to k and is often smaller than ABV
(see Section E.3
20
One Boxt 3-30 (AAA))
25
Enac us LLown Ed)
Boxt- --3000
Ease- (en))
3.5
ND Bost 1 (Stglar Bd.1
20
Road (san)
MV Easd (AA]
NV Bost (Lowe Bd.
coot
3/V Esad- 0.4 (C)
XVV Bost
10
10
30
40
10
50
10
20
30
Credit Dataset groups).
(b) COMPAS dataset (2 groups).
(c) Adult dataset (5 groups).
Figure 5: Comparison of our algorithm with exactly k centers with MV Makarychev and Vakilian
(02T). The max and min Subfigure (c) are across the groups and are used prevent cluttering plots with 5 groups.
17

---

Under review as a conference paper at ICLR 2023
E.2
RESULTS OF DIFFERENT ALGORIHTMM FOR DIFFERENT PARAMETERS
10
tu (Ler Ed1
Ben
02 (C)
(mm)
Onr tien - (Leve Ed
Our ties A ud (Huue 3d
18
Bon (AA)
Bon
-De (mm))
Oer Sten - (see)
Our bies + 1. (Lown Ed1
-Oe ster (200)
16
10
20
30
40
50
10
20
50
10
20
30
40
50
8:
(a) Credit Dataset groups).
(b) COMPAS dataset (2 groups).
(c) Adult dataset (5 groups).
Figure 6: Performance of our bicriteria algorithm for different values of X. The max and min on
Subfigure (c) are across the demographic groups.
ABV Baess (Higher
ABV (AN)
16
(oed)
ABV Dan 0.1 (C)
ABV Biess 0.3 Hiihe 5d
Ban (AA)
14
ABV Bee 03 (mec)
ABV Biczs 0.3 LLowe Ed))
-ABY Biei land)
ABV Biess (Bligaen
(AA)
12
ABV Bkn.
3
16
10
2.5
14
10
20
30
40
60
10
20
30
80
10
20
30
40
50
(a) Credit Dataset (2 groups).
(b) COMPAS dataset (2 groups).
(c) Adult dataset (5 groups).
Figure 7: Performance of our bicriteria algorithm of ABV Abbasi et al. of c. The max and min on Subfigure (c) are across the demographic groups
2021
for different values
14
Our Eact
6- (igiee
Our Boxt --09(A))
Our Exart 1- (ood)
Highs
Ove 3-361AM)
12
On Eass
1-00 Lowe: B1
Osx Buxi --x 1-36 (C)
Our Eass 1- (und)
Our East
Miden 31)
Oue Buxt- 2-10(AA)
Rust
10
Our Exse- (ass)
(umd)
2.5
14
2
12
40
50
20
1:
(a) Credit Dataset (2 groups).
(b) COMPAS dataset (2 groups).
(c) Adult dataset (5 groups).
Figure 8: Performance of our algorithm with exactly i centers for different values of X. The max and min on Subfigure (c) are across the demographic groups
MW Esss 61 Ollivee 30
Moxt 0.1 (AA)
26
3V Baxe n1 (nve)
(Lown E1
flase
(oto)
0.2 (AA)
-V Eass (Loor
MXY Mouet
0.2 (C)
20
MY Blair (o00)
MP Eowe 0d (ffilve S51
00 (AA)
MP Basi n. (reed)
Fowt (Looe E.1
MV Flas - (mro)
15
10
2
12
(a) Credit Dataset (2 groups).
(b) COMPAS dataset (2 groups).
(c) Adult dataset (5 groups).
Figure 9: Performance of our MV algorithm Makarychev and Vakilian 2021 for different values of 7. The max and min on Subfigure (c) are actoss the demographic groups
18

---

Under review as a conference paper at ICLR 2023
E.3 NUMBER OF SELECTED CENTERS IN THE BICRITERIA ALGORITHMS
The number of selected centers for our bicriteria algorithm on the Credit dataset. is parameter of the algorithm and denotes the amount of decrease in radii of balls around the clients in the iterative rounding algorithm.
Table 1:
0.2
0.4
0.6
À
0.8
À
1.0
6
6
k 10
11
11
11
10
11
15
15
15
k: 20
21
21
21
20
20
k 25
26
26
26
25
25
k 30
31
31
30
30
k 35
36
36
35
35
k 40
41
40
40
40
40
45
46
45
45
46
50
50
50
50
51
51
Table 2: The number of selected centers for bicriteria algorithm Abbasi-Bhaskara- Venkatasubramanian Abbasi al.) (2021) on the Credit dataset. is a parameter of the algorithm. The maximum number of selected centers is k/(1 (1- E) which achieves a 2/e approximation factor.
c
0.1
0.2
c =
0.3
0.4
c
0.5
h:
5
7
k 10
11
12
14
16
20
= 15
16
18
21
23
29
20
23
26
29
34
k 25
22
27
31
35
39
b = 30
29
34
37
41
46
25
29
36
40
45
k 40
26
30
38
43
48
45
36
40
46
53
59
38
51
58
64
Table 3: The number of selected centers for our bicriteria algorithm on the COMPAS dataset. À is parameter the algorithm and denotes the amount of decrease in radii of balls around the clients in the iterative rounding algorithm.
0.2
0.4
0.6
X
0.8
X
1.0
6
6
b 10
11
10
11
11
10
k 15
16
16
16
16
16
20
21
21
20
20
h 25
26
26
25
26
26
k 30
31
31
31
31
31
35
36
36
36
h 40
40
41
41
41
40
k 45
46
46
46
46
46
50
51
51
50
19

---

Under review as a conference paper at ICLR 2023
Table 4: The number selected centers for bicriteria algorithm
Venkatasubramanian Abbasi et al. (2021) the COMPAS dataset. is parameter of the algorithm. The maximum number of selected centers is k/ <) which achieves a 2/c approximation factor.
0.1
0.2
6
0.3
0.4
6
0.5
k
5
7
10
E = 10
11
12
14
15
16
= 15
16
18
19
20
21
k 20
22
24
24
25
27
à = 25
27
29
30
31
32
= 30
30
34
35
36
38
k 35
35
40
40
42
43
k 40
42
46
48
49
51
45
51
52
53
k 50
50
56
58
59
61
Table 5: The number of selected centers for our bicriteria algorithm the Adult dataset with groups. is parameter of the algorithm and denotes the amount of decrease in radii of balls around the clients in the iterative rounding algorithm.
0.2
À
0.4
A
0.6
X =
0.8
À
1.0
h 5
7
7
7
h 10
15
14
12
k 15
18
15
18
14
19
k 20
24
20
22
18
20
k 25
30
27
25
28
k 30
34
34
33
30
33
35
38
38
38
35
38
40
43
43
40
44
b: 45
45
47
47
45
46
k 50
54
54
54
54
50
Table 6: The number selected centers for bicriteria algorithm Abbasi-Bhaskara- Venkatasubramamian Abbasi et al. (2021) on the Adult dataset with 5 groups. is parameter of the algorithm. The maximum number selected centers is k/(1 <) which achieves a 2/c ap- proximation factor.
0.1
0.2
0.3
0.4
0.5
F
4
5
6
7
6
10
11
k 15
9
10
11
12
13
20
13
13
15
15
17
19
20
22
k 30
18
19
21
23
28
}: == 35
22
25
29
32
37
30
39
45
k 45
45
51
57
61
68
b 50
45
50
56
61
68
20

---

Under review as a conference paper at ICLR 2023
Table 7: The number of selected centers for our bicriteria algorithm the Adult dataset with 10 groups. À a parameter the algorithm and denotes the amount of decrease radii balls around the clients in the iterative rounding algorithm.
À
0.2
X
0.4
0.6
À
0.8
À
1.0
9
9
9
k 10
20
18
19
17
18
k 15
23
24
22
16
22
k 20
30
27
20
23
k 25
32
35
34
25
26
k 30
38
38
36
31
30
35
44
45
43
35
k 40
48
47
44
48
49
k 45
51
52
51
50
51
50
57
59
57
53
Table 8: The number of selected centers for bicriteria algorithm of Abbasi- Bhaass-- Venkatasubramanian Abbasi et al.) (2021) on the Adult dataset with 10 groups is parameter of the algorithm. The maximum number of selected centers is k/(1 e) which achieves 2/c ap- proximation factor.
=
0.1
0.2
=
0.3
=
0.4
=
0.5
k
2
6
6
k
10
5
8
10
b = 15
7
9
11
12
11
12
14
15
k 25
13
15
16
18
22
= 30
18
20
23
28
31
22
26
29
33
38
k 40
26
35
40
42
46
F: 45
40
46
53
56
61
50
39
55
62
69
21

---

Under review as a conference paper at ICLR 2023
E.4
COMPARISON OF RUNNING TIME DIFFERENT ALGORITHMS IN PRACTICE
Table 9:
Comparison of the running time of different algorithms on the first 200 samples of the
Credit dataset averaged over five runs.
Our Bieriteria
Our Bicriteria
ABV
ABV
MV Exact
MV Exact
Our Exact
Our Exact
k
Bicriteria
Bicriteria (<=0.4)
(A20.2)
(A=0.6)
(A=0.2)
(A=0.6)
(e (.3))
( (7=0.1) 0.11
(7 0.2)
20
11.12
13.20
12.21
11.07
11.56
13.28
33.42
30.41
25
13.20
13.67
11.51
12.20
14.06
14.51
34.04
36.52
30
4.42
10.32
4.59
3.64
4.53
10.40
20.59
15.28
35
3.60
3.74
4.53
3.89
4.27
5.88
21.97
23.35
40
5.57
3,86
4.23
3.62
7.92
6.09
16.33
19.77
Table 10: Comparison of the running time of different algorithms on the first 200 samples of the COMPAS dataset averaged over five runs.
Our Bicriteria
Our Bieriteria
ABV
ABV
MV Exact
MV Exact
Our Exact
Our Exact 0.6)
k
Bicriteria
Bicriteria (<=0.4)
(A= 0.2)
(A 0.2)
(A= 0.6)
(e=0.3)
(y=0..1
(y = 0.2)
20
7.98
7.19
6.51
8.81
6.22
44.18
45.13
25
4.88
4.72
7.04
5.36
5.88
5.75
39.68
38.47
30
4.83
5.60
5.14
3,98
6.26
6.91
35.15
37.71
35
5.83
6.74
5.91
6.33
7.27
8.22
34.29
35.85
40
5.37
5.21
5.87
6.13
6.82
6.03
39.59
43.49
Table 11: Comparison of the running time of different algorithms the first 200 samples of the Adult dataset with race groups averaged over five runs.
Our Bieriteria
Our
ABV
ABV
MV Exact
MV Exact
Our Exact
Our Exact
k
Bicriteria
Bieriteria
Bicriteria (==0.4)
(A=0.2)
(A=0.6)
(A=0.2 0.2)
(A=0.0
(e 0.3)
(y=0..1 0.1)
(7 = 0.2)
20
13.31
12.88
11.96
11.28
17.01
19.69
73.09
75.06
9.86
11.35
10.74
12.54
16.73
18.3
54.87
55.06
30
7.36
8.36
8.24
9.10
15.04
14.85
44.91
47.48
35
6.91
8.09
6.10
6.84
11.74
14.45
40.51
36.48
40
5.76
4.12
5.47
4.69
8.12
6.42
24.69
23.54
Table 12: Comparison of the running time of different algorithms on the first 500 samples of the Adult dataset with 10 and gender groups averaged over five runs.
Our Bieriteria
Our Bieriteria
ABV
ABV
MV Exact
MV Exact
Our Exact (A=0.2)
Our Exact
Bieriteria
Bieriteria
(A 0.6)
(A= 0.2)
(A=0.6)
(e (e=0.3) 0.3)
0.4)
(y=0.1)
(y = 0.2)
20
166.2
159.7
136.5
125.5
414.3
212.5
$97.0
686.2
25
171.7
195.0
165.3
149.2
250.3
254.4
753.3
679.2
30
185.1
150.3
152.6
163.5
335.3
153.5
690.1
690.5
35
176.5
176.3
178.4
175.9
265.4
183.3
786.8
795.5
40
168.7
170.2
157.6
181.4
223.6
199.7
867.8
816.6
22


Reviews:
[{"review_id": "hIr5nBVkhB", "reviewer": "Reviewer_3GL3", "summary": "", "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": "", "summary_of_the_paper": "This paper focuses on the socially fair k-clustering problem. The problem is well-motivated and considers a fair version of the three important and interesting clustering problems, i.e., k-median, k-means and k-center. The authors present four results:\n\n1- A bi-criteria $(9.9)^p$-approximation algorithm that opens (k+m) centers.\n2- A $(9.9)^p$-approximation algorithm with running time $O(n^{2^{O(p)} m^2})$.\n3- A $(30)^p$-approximation algorithm with running time $k^m poly(n)$.\n4- Empirical comparison of their algorithm with the baselines.\n", "summary_of_the_review": "The algorithm and theoretical results in good, but there is a concern regarding the performance of the algorithm in larger datasets.", "strength_and_weaknesses": "The main result of this paper is interesting and although some ideas are not novel, they are used in a nice way. It is not clear to me the improvement that we are getting with respect to the previous work. With respect to the number of centers opened, the previous work opens a factor $(1+\\epsilon)$ more but this work opens an additive $m$ more centers, this can be more or less depending on the setting, but assuming that $m$ is significantly lower that $k$ makes sense to me. Which means that the result can be considered stronger with respect to the number of centers it opens. From the approximation point of view, it is not clear to me which work is better. What is the hidden factor in the approximation guarantee of Abbasi et al?\n\nThe ideas in the second and third results are also interesting and the sparsification is nice. I do not think these results are as strong as the main result but definitely a good additional result.\n\nThe main weakness of this paper is the experiments, the main concern being the size of the datasets. The size of the considered datasets are rather small and in some cases the algorithm is slower than the baseline. Is it possible to run the bi-critria algorithm of larger datasets, say 100K points or more? The cost improvement over the baselines are significant and interesting. I think it helps to add the exact number of the centers opened by each algorithm in the main body of the paper (it can be added to the same plot as cost as well). \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "RMDBcE9a-lO", "reviewer": "Reviewer_8wgV", "summary": "", "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": "", "summary_of_the_paper": "This paper studies approximation algorithms for the socially fair clustering problem. In the socially fair clustering problem, the input is a metric space, n data points, m groups of the n points whose union is n but may not be disjoint, and an integer k, the goal is to find a set of k center points C from the metric space, such that the maximum (\\ell_p, k)-clustering cost among all groups, is minimized. Here, the (\\ell_p, k)-clustering cost is the sum of p-th power of distances from every data point to a center C.\n\nThe paper focuses on the case when m is small. In particular, it gives two O(1)-approx algorithms, one runs in poly(nkm)-time but returns k + m centers, and the other returns exactly k centers but runs in (nk)^{poly(m)} time (or poly(n) k^m for a slightly worse constant ratio). Experiments have been conducted to compare the empirical performance of the proposed algorithms to recent works. The main observation is that the proposed algorithms generally have a better ratio, this is especially true when the number of clusters k is large.", "summary_of_the_review": "The theory part of the paper is interesting, but I recommend a weak reject overall since the impractical nature of this algorithmic work makes it less relevant to the audience of ICLR.", "strength_and_weaknesses": "# Strength:\n\nThis small-m-O(1)-approx regime seems to be new, since previous results either violate the number of centers k by a multiplicative factor (which may be much larger than m when m is small), or is super-constant approximation. The results are obtained using LP-rounding techniques that were mostly developed in previous works for related problems, but I find the adoption of them nontrivial.\n\n# Weakness:\n\nThe algorithms do not seem to scale on larger data sets, thus is not quite practical. For instance, even with only 200 - 500 samples, the running time is already tens - hundreds of seconds (as reported in Section E.4). Also, the current baselines are mostly previous approximation algorithms. What about considering some naive baselines? For instance, what if one uses CPLEX to solve the integer program exactly, is the running time indeed very much worse? For vanilla k-clustering, often sub-sampling based preprocessing can applied, so I’m wondering what about first doing a uniform sample of the points, and then apply all these algorithms only on the sample to obtain a set of centers?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "0uKXEcRHHd", "reviewer": "Reviewer_hqAh", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "", "summary_of_the_paper": "The problem considered is a “socially fair” variant of (l_p,k)-clustering algorithm. Specifically, the goal is to compute k points, given N points grouped into m classes such that the max weighted sum (for a given weight vector) of L_p metric distances of each group  is minimized over all groups. The central result is a bi-approximation algorithm for this problem where a const^p approximation guarantee is achieved at the expense of m additional centers. \n\nThe key prior results for this problem include a:\n\n1.\tConst^p*log m approximation guarantee (Makarichev and Vakilian), with a matching lower bound result (under a complexity assumption)\n2.\tBiapproximation algorithm with 2^O(p)/epsilon approximation guarantee but using k/(1-epsilon) centers.\n\nThe current work improves the second result in the case where m << k.\n\nFurther, using sparsification techniques developed by Li and Svenson, they show that the additional centers can be removed at the expense of a quasi-poly time.\n", "summary_of_the_review": "Overall, I think while the bi-approximation guarantee result is interesting, the techniques seem to be incremental. On the other hand, the sparsification result is perhaps of some mathematically more interest, but the result may be somewhat pedantic and unimportant. ", "strength_and_weaknesses": "The bi-approximation result is based on an iterative rounding technique developed by Krishnaswamy et al. Over the iterations, the LP is modified by changing relevant constraints and finally they obtain an LP that is shown to be an intersection of a matroid polytope and m affine spaces. Thanks to a classic result by Grandoni, this implies that the optimal solution for this LP has a support size k +m. Simply rounding these positive fractional variables yields a solution of size k+m centers. \n\nThis method seems to be essentially a combination of existing techniques/results, and therefore I would really appreciate the distinctions/comparisons between the current approach and that of Krishnaswamy et al. If it’s just applying the techniques known techniques to a slight generalization – the result would be rather incremental in my opinion.\n\nThe sparsification appears to need some careful enumeration but I am not able to judge the importance of the result. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject