Parameterized Approximation Schemes for Fair-Range Clustering
Authors: Zhen Zhang
Xiaohong Chen
Limei Liu
Jie Chen
Junyu Huang
Qilong Feng
Venue: NeurIPS 2024 poster (2024)
Keywords: Approximation algorithms
Fixed-parameter tractability
Primary area: fairness

Abstract: Fair-range clustering extends classical clustering formulations by associating each data point with one or more demographic labels. It imposes lower and upper bound constraints on the number of facilities opened for each label, ensuring fair representation of all demographic groups by the selected facilities. In this paper we focus on the fair-range $k$-median and $k$-means problems in Euclidean spaces. We give $(1+\varepsilon)$-approximation algorithms with fixed-parameter tractable running times for both problems, parameterized by the numbers of opened facilities and demographic labels. For Euclidean metrics, these are the first parameterized approximation schemes for the problems, improving upon the previously known $O(1)$-approximation ratios given by Thejaswi et al. (KDD 2022).

Parameterized Approximation Schemes for Fair-Range Clustering
Zhen Zhang Xiaohong Chen 1.2,* Limei Liu 12, Jie Chen Junyu Huang", Qilong Feng3.2
National Key Laboratory Cultivation Base for Data Intelligence and Smart Society,
Hunan University of Technology and Business, Changsha 410205, China EXiangjaag Laboratory, Changsha 410205, China
3 SScooo of Computer Science and Engineering. Central South University, Changsha 410083, China
edu. chemj ay edu. en, junyuhuang@csu. edu, cn, csufengemail csu, edu,
zz@hutb. edu. en, csu cxh@163. com, seagullm0163, com,
Abstract
Fair-range clustering extends classical clustering formulations by associating each data point with one or more demographic labels. It imposes lower and upper bound constraints on the number of facilities opened for each label, ensuring fair representation of all demographic groups by the selected facilities. In this paper we focus on the fair-range k-median and k-means problems in Euclidean spaces. We give (1 + -)-approximation algorithms with fixed-parameter tractable running times for both problems, parameterized by the numbers of opened facilities and demographic labels. For Euclidean metrics, these are the first parameterized approximation schemes for the problems, improving upon the previously known ( (lLa)apppxximttionn ratios given by Thejaswi et al. (KDD 2022).
Introduction
Clustering seeks to partition given set of clients into disjoint, cohesive clusters. Among the many formalizations of clustering, the k-median and k-means problems are perhaps the most prevalent ones, owing to the concise nature of their descriptions. Given a set of clients and facilities in metric space along with positive integer k the k-median and k-means problems aim to open at most facilities and connect each client to the nearest opened facility, such that the sum of the client-connection costs is minimized. In the k-median problem, the connection cost of each client is its distance to the corresponding facility, while in the k-means problem, it is the squared distance. Despite their seemingly simple definitions, the k-median and k-means problems are computationally challenging, and the development of their approximation algorithms continues be vibrant of research. The current best approximation guarantees are the ratios of 2.613 [Gowda et al. 2023 for the k-median problem and 9 [Ahmadian et al. 2020 for the k-means problem.
The k-median and k-means problems are designed to maximize similarity between clients and their corresponding facilities, allowing the opened facilities to be considered representative points for the client set. This understanding underscores the important roles that the k-median and k-meaas problems play in data summarization [Moens et al. 1999 Girdhar and Dudekl [002]. However, algorithms developed for these problems can often yield unfair summarization of socioeconomic data, as they prioritize minimizing the clustering costs over considering the distribution of demographic labels g., gender, age, race) associated with the opened facilities [Ka et al. 2015). Driven by this
Corresponding Authors
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

rationale. there has been considerable interest in fair-range clustering. Given a set of data points associated with demographic labels, fair-range clustering extends classical clustering formulations by imposing lower and upper bound constraints on the number of opened facilities associated with each label, thereby ensuring fairness across different demographic groups.
3, p. 7) of the fair-range clustering problem specified by positive integers An instance kf C.F, F,,, l and h. sets C of clients and F of facilities in a metric space, vectors ā = (a),- ,a)) and {1.... ,{), and integer 2 1, where each f E F is associated with a set r(f) C {1,-.. , of demographic labels. A feasible solution to the instance specified by subset H S F of no more than k facilities satisfying |[/ E H E T(SH E [ov,, 3c] for each / E {1, f, and the cost of the solution is Eeec minjen (e,, f), where is the distance function. The goal of the fair-range clustering problem is to identify a feasible solution with minimum cost.
3 (f,,..., ,Be) of l positive integers satisfying at Be for each
The fair-range clustering problem is equivalent to the fair-range k-median (FkMed) problem when 1, and to the fair-range k-means (FkMeans) problem when p = 2. Despite their significance in applications requiring fair representations, the FkMed and FkMeans problems pose significantly greater computational challenges than classical clustering problems. As demonstrated by Thejaswi] et al. [202T]. J. designing polynomial-time algorithms with provable approximation guarantees for the FkMed and FkMeans problems is unlikely, as determining the existence of feasible solutions to their instances is NP-hard. For simplified scenario where each facility is associated with a single demo- graphic label, Thejaswi et al. 2021] showed that the FkMed and FkMeans problems can be reduced to the well known matroid clustering problem, which admits constant factor approximation algorithms Krishnaswamy et al., 2011
Li 2011] Swanyy 2014 Friggstad and Zhang, 2016,] Krishnaswamy al. 2018 albeit with an O(k) multiplicative overhead in algorithmic running time. Hotegmi
et al..] 2023 latter gave an improved reduction to the matroid clustering problem that eliminates the O(k) overhead. They further demonstrated that solving the FkMed and FkMeans problems in this simplified scenario can be achieved even more efficiently than solving matroid clustering problems, based on smaller-size linear programs,
In practical scenarios concerning clustering problems, the number of opened facilities (i.e., k) is often considerably smaller than the input size. As such, assuming k to be small and treating it fixed parameter is commonly used way for simplifying these problems, as exemplified in Gohen-AAdaa al. 2019 Goyal and Jaiswal 2023 Chen et al. [0224] 2024|aissal Jaiswal et al. 2024]. Unfortunately. the FkMed and FKMeans problems have been demonstrated to remain challenging even with this simplification: When both 1: and the number of demographic labels (i.e., E) are fixed parameters, Thejaswi et al.) [202)] established the W[2]-hardness of the FkMed and FkMeans problems, suggesting that exactly solving them in -peemmpareeetr tractable time (denoted as FPT(K, time, meaning n ( (k, E) for input size of and positive function h) is unlikely: mnlikely:CCoen-Addae (odee-AAdad al. [209)] showed that the best possible approximation ratios of FPT (ks f)-time algorithms, even for the case where = 1. cannot be better than + 2e for the FKMed problem and + Se for the FkMeans problem. This matches the FPT time (1 + 2e + appppooxiintooon algorithm for the FkMed problem and (1+ 8e-1 + appproxiimtio algorithm for the FkMeans problem given by Thejaswi et al. [2022) for simpler case considering only the lower bound constraint. Notably, the method for enumerating feasible constraint patterns given by /Thejaswi et al. [2022] demonstrates that their algorithms can be effortlessly extended to accommodate the case involving both lower and upper bounds.
The negative result presented by Cohen-Addad et al. 2019 suggests that we cannot hope ap- proximate the FkMeans problem with a ratio better than 1 Se and the FkMed problem with a ratio better than + 2e in FPT(K, E) time when considering general metric spaces. However, this result does not preclude the possibility of achieving better approximations for these problems in more structured settings, such as Euclidean spaces, since the analysis in CCCohenAAdaa et al. [019]] is limited to general metrics. In this paper, we take the first step toward exploring the properties of Euclidean metrics for the FkMed and FkMeans problems. Our approach yields (PT t)-time approximation schemes, as stated in Theorem I in Section 3.4
1.1 Other Related Work
Due to the prevalence of Fuclidean data in real-world applications involving clustering, significant attention has been devoted to developing algorithms that leverage the properties of Euclidean spaces.
2

---

Exploring these properties often leads to improved approximation guarantees. One such example can be found in [Cdden-Addad et al. 2022], where (2.406 + =apppooxxiiatoonn algorithm for the k-median problem and a (5.912 + 8 approximation algorithm for the k-means problem in Euclidean spaces are proposed, improving upon the state-of-the-art approximation ratios for these problems under general metrics [Gowda et al.] 2023 Ahmadian et al. 2020]. Furthermore, it has been shown that the Euclidean k-median and k-means problems admit approximation schemes 2 if A a fixed parameter and the opened facilities can be located arbitrarily [Kumar et al. 2010 Jaiswal et al. 2014 Bhattacharya et al. 2018, Ding and Xu 2020]. These algorithms identify a subset of each client-cluster defined by an optimal solution and approximate the corresponding opened facility by the centroid of this subset. However, similar ideas are not applicable to the FkMed and FkMeans problems, as they involve finite sets of facilities and hard constraints on the labels of the opened facilities, In these cases, the centroids of the considered subsets are not guaranteed to be feasible as opened facilities.
Constraints on the number of opened facilities associated with different labels were first introduced by Hajiaghayi et al. 22010, 2012]. inspired by budget considerations for the deployment of servers in content distribution networks. From then on, related clustering problems have been widely explored. When we are provided with an upper bound constraint and each facility is associated with a single label, the problems represent special cases of the matroid clustering problems and directly motivate research into the latter (Krishnaswamy et al. 2011). For the sower-boudded case, there are FPT k. E)- time approximation algorithms for the k-median and k-means cost functions (given by Thejaswi ct al. 2022]. , previously mentioned in Section [[] and multi-swap local-search heuristic yields an ( approximationnn for the k-median cost function if each facility has single label (Thejaswi et al. 202 Zhang et al. 2024..
In addition to imposing constraints on the distribution of labels associated with opened facilities, fair clustering has been extensively studied under various other settings that introduce different types of constraints. For example, group fairness requires each cluster to provide a fair representation of
different demographic groups [Chierichetti et al. 2017 Bera et al. 2019 Bandyapadhyay et al. 2021
Dai et al.) 2022, Wu et al., 2024], proportional faireess ensures that no subset of clients, of a given size, find closed facility that provides lower connection cost to each of its members [Chen
ct al., 2019 Micha and Shah 2020), individual fairness requires that the distance from each client to
the nearest opened facility does not exceed a client-specified threshold [Jung et al. [2200] Mahabadi
and Vakilian 2020 Negahbani and Chakrabarty 2021] Vakilian and Yalçiner] [0022AAmmad et al.
2022 Bateni et al. 2024], and social fairness aims to minimize the maximum clustering cost among
groups of clients Abbasi et al.
2021 Ghadiri et al. 2021 Makarychev and Vakilian 2021 Goyal
and Jaiswal 2023
Abbasi et al. 2024
1.2
Preliminaries
From now on, we consider an instance I = (e,k,C,F.,, T. of the fair-range clustering problem satisfying p E 21, [CUF = n, and C CUFC C IRd, along with a constant E (0, 0.5). Given an integer 2 1 and set D, define [i] {1, i), and let [D] be the Cartesian product D x D.
Given a point x and a set P of points in an Euclidean space, let 6(x, P) = minpe || pll denote the distance from x to its nearest point in P, and let 6a(x, P) = minper ||z pll for each 2 1.
The following algebraic fact will be utilized in the analysis of the running times of our algorithms.
Lemma Given two real numbers and greater than 1, we have log' S max (xxx))(0()))
The following lemma extends triangle inequality Io squared Fuclidean metrics.
Lemma 2 Given three points x, y. and in Euclidean space and real number 7 E (0, 1]. we have ||x - 2|12 < (1 + > yll + (1 + 71yy 2|1?.
We will also consider the weighted version of the fair-range clustering problem, which can be defined as follows.
2 An approximation scheme is a (1 + e) =)aaproxximation algorithm, where e is an arbitrary small constant.
Given three points æ. y, and in Euclidean space, have |/e- =|| I || yll + lly 2|].
3

---

Figure 1: (a) The client nearest to the opened facility f is taken as the leader, around which an annular search space is constructed; (b) the center point / is opened in our solution.
Definition (weighted fair-range clustering) An instance (,,
of the fair-range
clustering problem can be extended to its weighted version kk, F, P.T. w) by associating each client C with weight wi() 1. This extension modifies the cost of a feasible solution H C F from Leec (c, H) to Eeec w(c)) H).
2
An Overview of Our Algorithms
The FPT(K; 4-time approximation algorithms for the FkMed and FkMeans problems given by The- jaswi et al. [2022) follow the framework outlined in [Cohen-Addad et al. 2019]. This framework identifies the nearest client each facility opened in the considered optimal solution
"leader" and introduces set of annuli centered at cach leader. Each annulus is defined such that its outer radius is + æ times its imner radius. The framework then enumerates the annuli identify those that contain the facilities corresponding to the leaders and selects the opened facilities within these annuli, as illustrated in Figure (a). Intuitively, the definition of the annuli and triangle inequality imply an upper bound on the distances from the selected facilities to the optimal ones. Building upon this insight. [hejaswi et al. [2022] utilized submodular maximization method to select facilities to be opened within the annuli and demonstrated constant-factor approximation ratios.
We similarly base our algorithms the framework proposed by Cohen-Addad al. 2019) Our approach focuses on exploring the properties of Euclidean metries to further refine the selection range of opened facilities. Specifically, we partition each annulus into a set of smaller cells: for each facility opened in the optimal solution, we select the center point of the cell containing it as the facility to be opened, as shown in Figure (bb) This process involves carefully balancing the number of cells, which affects the time required to identify the desired cells, against the sizes of the cells, which influence the distance from each facility opened in the optimal solution to the center point of the cell containing it, as well as our approximation ratio. We achieve this trade-off by constructing nets as defined below.
2003) Given density parameter ? 0, a set P C Rd and subset R C P. we call R a 7y-net of if each p E R satisfies 5(p, (((p)) 2 y and each E 'p satisfies 5(p, R) < 7.
Definition 2 (ry-net [Gupta et al.
We partition the annular search space into cells using set of nets for the facilities. The trade-off between the number and sizes of the cells can be managed by adjusting the density parameters (i.e., the parameter À in Definition D) For each annulus centered around a leader and containing its corresponding facility (the one opened in the optimal solution), we estimate the demographic labels associated with this facility and identifyy the subset of facilities within the annulus that share these labels. A net is then constructed for this subset, using a density parameter carefully determined by the radius of the annulus. Given the Voronoi diagram defined by the net, Definition 2 suggests that the facility opened in the optimal solution is close to the center point of its corresponding Voronoi cell. By considering each member of all constructed nets candidate for opened facility, can ensure that the candidate set includes a subset closely approximating the optimal solution.
It remains to consider how to bound the running time within FPT(K, E) time. The algorithms given by Cddad al. [2019] Thejassi et al. (2022) start with constructing a coreset, that is, small weighted subset of the client set whose distribution closely approximates that of the full set.

---

This facilitates the efficient identification of leaders by enumerating the coreset. In this paper, we face additional challenges in bounding the running time. For instance, when partitioning the annuli into cells, the number of cells can depend exponentially on the spatial dimension. To ensure that we can deal with the FkMed and FkMeans problems high-dimensional Fuclidean spaces within FPT E) time, we map the considered instance to a space of Olog k log log n) dimensions using combination of the method for constructing coresets given by Chen [2009] and Johnson- LinddsonnLnddsssrruuss transform. Combining this data-reduction technique with our net-based approach for selecting opened facilities, we give FKT t)-time (1 + s)-approximation algorithms for the FkMed and FkMeans problems.
3 The Algorithms
We now present our algorithms for the FkMed and FkMeans problems. In Section 3.1 we introduce our data-reduction method for decreasing the size of the considered instance. Section 3.2] we construct annular search spaces for the facilities to be opened, using the leaders from the client set. Section 3.3
details the construction of nets for the facilities, based on which we provide approximation schemes in low-dimensional spaces. Finally, in Section 3.4 we show how to combine the data-reduction method with the algorithms designed for low-dimensional spaces to deal with high-dimensional instances of the FkMed and FkMeans problems.
3.1 Data Reduction
In this section we map instance I to a smaller weighted instance in a low-dimensional space. As mentioned in Section 2 we achieve this using the coreset-construction method given by Chen [2009]
and Lindesst-nndeestrauuss transform, which are detailed the following two lemmata.
Lemma (Chen 2209)) Given constant E 0.5), a set P C. IRd an integer > O. and
an integer p {1, 2), subset pt C with a weight function w pp - [1,+00) satisfying
[Pt| S d(te= -1 log (P)) and EpEpt w(p) = (Pl can be constructed in O(PPldt) time, such that
each H C Rd with HH| < t satisfies Epept (()) H) E [1-c,1 Epep (p, H).
Lemma 4 (Jhnsonn and Lindenstrauss 1984), Ailon and Chazelle (2009) Given a constant 6 (0, 0.5) and a set P C Rdd we can construct mapping & Rdd -> RRd satisfyyng d = O(c 2 log (P)) and (p(p)) p(22)l e [1.1 dl forl each Pr. P2 E P in Od d) (c log (P)) time.
The following lemma is stronger version of Johnson-Lindenstrran Lindenstrauss transform, which preserves distances over broader range through terminal embedding. Specifically, modifies the condition "for each P1, E PP" in Lemma to "for each p1 E P and p2 E IR
Lemma 5 Narayanan and Nelson (2019] Given a constant 6 E (0, 0.5) and a set P c Rdd we construct mapping @ Rdd + Idd satisfying d = O log (P]) and [1p(pı) (p(2)) [1, 1 + e]lppr - p2ll for each p1 E P and p2 E Rdd in (PPld-110(1) time.
It can be assumed that each mapping ; IRd + Rd constructed by Lemma 4 and Lemma 5 is injective. Such an assumption is made without loss of generality: We can create duplicates of the points in dd that have multiple preimages under yp This ensures that we can always differentiate poxx and (P() for any two distinct points r and y in Rd, even if (zxx) and (oy) have identical values across all dimensions. Distinguishing the images of the points from Rd is essential in fair-range clustering problems because points with the same dimensional values can have different demographic labels.
Our data-reduction method, which combines Lemma 3 Lemma and Lemma is presented in Algorithm I and illustrated in Figure (this figure outlines the processing flow for the clients). This algorithm first leverages Lemma within the Oglog dimeensional space constructed by Lemma 4 such that the client set can be replaced with a coreset of size logarithmically dependent on n and independent of d. Next, to reduce dimensions while preserving the distances between each client in the coreset and any facility, Algorithm I usee Lemma 5 with the coreset input to construct an Olog k + log log dimmensnsol space. The following lemma provides the performance guarantees of Algorithm 1.
5

---

Algorithm 1: The data-reduction method
Input: A constant E (0, 0.5) and instance F,,,C.F,,,,,.... of the fair-range clustering problem satisfying C U F C R
Output: A mapping yp _ R and an instance F,,, p.T,w) of the weighted fair-range clustering problem satisfying p (1,2). C CUF CR.
F = {p( E F}, and ((p(f) = =f() for each E
Let 9p1 : _R + Rdd be the mapping constructed by Lemma with (c,C U.F) as the input; Let C be the weighted constructed by Lemma with (c, (c)( c Cj k. p) the input,
and let w Ct + [L. +oo) be the corresponding weight function;
Let 422 Idd + R be the mapping constructed by Lemma 5 with (e, Ct) as the input;
p - 42 pp. C = ( )"), F = {f((f) FF
return y Rd Rdd (L,k,,,F, B. wl )
(pi(c)
Figure 2: Given a set C C Rdd clients, Algorithm first maps to Id' using mapping Φ1 Rd Rdd, It then constructs a coreset Ct for (c)((c) e E C). Finally, the algorithm maps Cf to Rd using mapping P22 : Rdd Rd
Lemma 6 Given conslant 00,).5) and an instance C,F,F,F,,BBB.. P.T.) of the fair-range clustering problem with e {1, 2}. |CUF|= n, and C CF C. Rd. Algorithm constructs a mapping pp Rd I and instance (e, k, C ā, B.p.T. w) the weighted fair-range clustering problem in (dlog d) (nke-1) time, which satisfy the following properties:
() Eose w((c) |C),
(ii) w(c) 2 1 for each E č,
(ii) [C| & (kE -ke--llogo log 01))
(iv) d d= = o11) k log n). and
(v) Eeer (c))o((c, (p(f) f E HB) e, (1 e)2ot1| 1 EE (0 H.) for each H. S F with H k.
3.2 The Annular Search Spaces
In this section we construct annular search spaces, each corresponding to one of the facilities
to be opened. We first introduce some notations. Let yp Rd - Id be the mapping and = (e, k. F. a. P. w) be the weighted instance constructed by Algorithm input, where Č ČU Rd f (p(s):
| with (e, as the F). and each F satisfies T(p(S)) Tf)) Let H' -.. }ft be an optimal solution to I, and let opt Eced w(c)d" H²) denote its cost. For each E [k). let L, = [ E $ +() = r(f))} denote the set of facilities that have the same set of demographic labels as fr and let č; = {c E C arg min m |l cll = } be the cluster of clients defined by f. Given the lower bound constraint on the number of opened facilities, it may be the case that some facilities in H correspond to empty clusters. We thus define

---

Algorithm 2: The algorithm for constructing annular search spaces
Input: A constant E (0, 0.5), an instance I (L, F, ā, p,T, w) of the weighted fair-range clustering problem, and positive integer n
Output: A collection A.
A. < 0;
Let IDD be the power set of [e]:
3 for each f E F do
L ((f) be integer randomly and uniformly selected from [k];
for each (Di, D&) E [0)]*, k' [k], (c,,... ,de) [Ō] and
E' E fll?: e f F} do
if liE [k] e D E aat, St] earch
each E [E] then
for each i E k] do
5 = [ʃ E :::(()) :(} =
=;); D
for each i E [|]and]
| n do
10
A(i,j) = {f = C; |f - dlll
- E (c(1 +e)--1onn 1e(1 +))6' =
A(i,0) = if C :1f:ffff- - s e6'n 1;
11
for each (Ji,... jr( E (l[e-2log m|] U (0))*' do
12
13
for each E [k'] do
14
A - {ʃ E A(i,
: :)( i}:
15
for each i [[]]]]]]]]]]]]]]]]]]]]] do
16
(f C n(f) = i] # 0 then
17
Let A, be singleton subset of (f E C. nff) = =i};
18
else
A 0;
20
A [{Ai, A+])
21
return A.
I : 0} and म A.. Let k [74 Without loss of generality, we can assume that FC = -......... }.-}.
Following the framework given by Cohen-Addad et 2019, we select opened facilities from set of annuli centered around a group of leaders from For each E [k*], let c denote the client from Č nearest to fr that is, the leader corresponding to f;" Let 8 = max;g[[=]] (c,,,, f:'). For each i e [K=]] and j E [[c log n1],. let (i. = {f E C. IIf lalle e +) 6 c(1 + e) &P 8f 1] be the set of facilities from L, located in an annulus centered around c₁ and let (i, = {ʃ E L. : ||ʃ -Gill < cdP maxx -11. The definitions of (i, and of imply the existence of an integer j (0.... .......... , log n] satisfying fi (i,,,)) Denote by Ai such A (i,j.) containing fü
Our method for constructing annular search spaces is presented in Algorithm 2 Since the collec- tion (1,,),)), k*, 50 6f and (c,,... Ck- Algorithm enumerates all possible values of these parameters in step 5 to ensure that the collection can be captured. Given an integer E [k*]] and the sets (i,, (i, [ log nl], Algorithm 2 enumerates [[c- log n U {0} in step 12 to find the integer with A = (i. To avoid the case where the search spaces for the k opened facilities intersect and the of selected facilities contains duplicate elements, Algorithm 2 eemploy a color-coding technique to eliminate any potential intersections. Specifically, Algorithm 2 associates each facility f E F with a random integer r)(f)) E [b]] in step 4, and only selects facilities with m(f) when constructing the i-th search space for each [k] in steps 14 and 17. The performance guarantees of this algorithm are presented in the following lemma.
[e-2 , [1) can be determined based on the values of [C,, Cx }. AA"",,,
Lemma The collection & constructed by Algorithm satisfies the following two properties:
7

---

Algorithm 3: The algorithm for low-dimensional weighted instances
Input: A constant E (0, 0.5), an instance I kL, C, C, ā, P.P,TT w,) of the weighted fair-range clustering problem, and positive integer n
Output: A solution Ht to I
A < 0, IH < 0;
for each s [k*] do
Let A' be the collection constructed by Algorithm with (e, n2) as the input:
A = A U A';
5 for each {AI,... ...... A E A with A, + DAiE do
for each E [k] do
[. = then
S - Ai:
else
10
Let S; be the m e||æ - y/l-net A, constructed by Lemma 8
11
Let H' be the collection constructed by transforming each tuple in S₁ x S2 x ... x S₁ into a
set;
12
HUM;;
13
return H + arg minHeR Eogê (c,) H).
( With probability no less than k- there exists collection (Ai, Ar} e A satisfying If E A, S AA for each E [k*] and A, + 0 for each [k]][k*);
(i) Given collection {A AA} An with Ar + @ for each E [k]. and tuple
(f,,.., .fk) E Ai x A2 x ... x Ak, we have Hi E [M] :t +(fi)] E [ar, Br) for each
te [0.
3.3 The Algorithm in Low-Dimensional Spaces
As outlined in Section 2 solutions are constructed by extracting nets from the set of facilities. The following lemma presents method for generating nets low-dimensional Euclidean spaces.
Lemma 8 Har--Plee and Mendel (2006)) Given a density parameter > O and set P C IR y-net of P of size most min maxp1.p2PP llp P2ll"} can be constructed in [P] log [P (0()) time.
Our approach for solving the low-dimensional weighted instance built upon Algorithm 2 and Lemma 88] and is outlined in Algorithm 3 Since Algorithm 2 yields the desired search spaces with probability - (as given by the first property stated in Lemma 7.. Algorithm 3 itteratively invokes k times, allowing the probability of successfully constructing the desired search spaces in least one of the iterations to be boosted to a constant, Given & sets AI, ... .As satisfying the first property stated in Lemma 7 Algorithm 3 constructs net for each set of size greater than and adds the members of the net to the candidate set of opened facilities. Finally, the algorithm constructs a set of feasible solutions to based on the candidates for opened facilities, and returns the one with the minimum cost among them.
The following lemma says that Algorithm 3 yields (1 + O aapproximation solution to Ý with high probability.
Lemma The following event occurs with probubility no less than 1 e1; Algorithm yields feasible Ht to I satisfying Eeer w(c))0(c, Ht) < 4c)ot if = and Eeeo w(() (c, H³) <
(1 (1+00 opp if 2.
By analyzing the time Algorithm takes to construet the set of candidate solutions, well as the
size of this set, we can establish the following upper bound on the running time of Algorithm B)
Lemma 10 Algorithm runs in more than khe fike---00 -10000 O(1) time.

---

Algorithm 4: The algorithm in high-dimensional spaces
Input: A constant E (0, 0.5) and instance I = F, of the fair-range clustering problem satisfying CUF CR² Rdd
Output: solution Ht to I
P, Let yp IK + _dd be the mapping and ī (l, k, (e,k, B, P. w) be the weighted instance constructed by Algorithm with (c, as the input:
2 Let H be the solution to constructed by Algorithm 3 with (c, (c,I,ICU (CUF) as the input;
3 return H < ()): E H!).
3.4 Extensions to High-Dimensionaa Spaces
We combine the data-reduction method given in Section 3.1 with the low-dimensional algorithm given in Section 3.3 to solve the FkMed and FkMeans problems in high- high-dimensional spaces, as detailed in Algorithm Given a constant algorithm starts with constructing a mapping &p : Rd + Rdd and small weighted instance I= (f, k. C,F, p, where C' U R , F = {p(() :f F}, and T(p(f)) rf) for each f E F. It then constructs solution to I and returns the set of preimages of the facilities opened in this solution under s. The analysis of the performance guarantees of Algorithm Saaamm/Jeaae leads the main result of this paper, as stated in Theorem [
0.5) and instance I (e, k, ā, B, r).
Theorem Given an instance (L, k. F, ā, B. p.T) of fair-range clustering with CUF c Rd and {1 along with real number E 1), there is randomized (1 + appproxximaioon algorithm running in Od d) + 2(ke +to 01)) time, where n = ICUFI.
4
Conclusions
In this paper, we consider the FkMed and FkMeans problems for the case where the numbers of opened facilities and demographic labels are fixed parameters. Based on combination of a data- reduction method and a space-pant poreceepatttioiingg approach for selecting opened facilities, we introduce (1++) approxxiiatioo algorithms in Euclidean spaces, representing the first parameterized approxi- mation schemes for the problems. Given that coreset-construction methods were known for many constrained clustering problems incorporating additional constraints on instances, such as those related to capacities [Cohen-Auee Addad and Li 2019], group fairness (Bandyapadhyay et al.) [222]]. and robustness [Huang et al. [2023]. J. an interesting direction for future work is to extend our techniques to deal with the FkMed and FkMeans problems in similar constrained settings. Another promising avenue for exploration is to accelerate heuristic algorithms for the fair-range clustering problem, such as those given in (Tejaswi al. 2022 using the data-reduction method proposed in this work.
Broader Impact
Our work deals with the fair-range clustering problem, providing algorithmic insights that can facilitate fair decision-making. While our algorithms have been shown to be "fair" according to specific definitions, essential to recognize that this faimess does not automatically warrant indiscriminate application. This underscores the need for careful consideration when implementing the algorithms proposed in this paper in real-world scenarios that prioritize fairness.
Acknowledgements
This work was supported by Open Project of Xiangjiang Laboratory under Grant Nos. 22XJ03013 and 24XJJCYJ01003, National Natural Science Foundation China under Grant Nos. 62202161, 62432016, 62172446, and 62202166 60, Natural Science Foundation of Hunan Province under Grant No. 2023IJ40240, and Central South University Research Programme of Advanced Interdisciplinary Studies under Grant No. 2023QYJC023.

---

References
Fateme Abbasi, Sandip Banerjee, Jaroslaw Byrka, Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoradi, Dániel Marx, Roohani Sharma, and Joachim Spoerhase. Parameterized approxima- tion for robust clustering in discrete geometric spaces. In Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, volume 297, pages 6: 161,999 2024.
Mohsen Abbasi, Aditya Bhaskara, and Suresh Venkatasubramanian. Fair clustering via equitable group representations. In Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, pages 504-514, 2021.
Saba Ahmadi, Pranjal Awasthi, Samir Khuller, Maithäus Kleindessner, Jamie Morgenstern, Pattara Sukprasert, and Ali Vakilian. Individual preference stability for clustering. In Proceedings of the 39th International Conference on Machine Learning, volume 162, pages 197-246, 2022.
Sara Ahmadian, Ashkan Norouzi-Farde Ola Svensson, and Justin Ward. Better guarantees for k-means and Euclidean k-median by primal-dual algorithms. SIAM J. Comput., 49(4), 2020.
Nir Ailon and Bernard Chazelle. The fast Jownsonn Lindenstrauss transform and approximate nearest neighbors. SIAM J. Comput., 39(1):302-333 2009.
Sayan Bandyapadhyay, Fedor V. Fomin, and Kirill Simonov. On coresets for fair clustering in metric and Euclidean spaces and their applications. Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, volume 198, pages 13:1-23:1,, 2021.
MossmmadHosseein Bateni, Vincent Coden-Addad, Alessandro Epasto, and Silvio Lattanzi. P Conference on Artificial Intelligence and Statistics, volume 238, pages 3151-3159, 2024.
scalable algorithm for individually fair k-means clustering. In Proceedings of the 27th International
Suman Kalyan Bera, Deeparnab Chakrabarty, Nicolas Flores, and Maryam Negahbani. Fair algorithms for clustering. In Proceedings of the 32nd Annual Conference on Neural Information Processing Systems, pages 4955 4965-4966, 2019.
Anup Bhattacharya, Ragesh Jaiswal, and Amit Kumar. Faster algorithms for the constrained k-means problem. Theory Comput. Syst., 62( -2(1))93-115. 2018.
Ke Chen. On coresets for k-median and k- k-means clustering in metric and Euclidean spaces and their applications. SIAM Comput.. 39(3):9233 2009.
Xianrun Chen, Dachuan Xu, Yicheng Xu, and Yong Zhang. Parameterized approximation algorithms for sum of radii clustering and variants. In Proceedings of the 38th AAAI Conference Artificial Intelligence, pages 20666-20673, 2024.
Xingyu Chen, Brandon Fain, Liang Lyu, and Kamesh Munagala. Proportionally fair clustering. In Proceedings of the 36th International Conference on Machine Learning, volume 97, pages 1032-1044 1041, 2019.
Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii. Fair clustering through fairlets. In Proceedings of the 30th Annual Conference on Neural Information Processing Systems, pages 5029-5037, 2017.
Vincent Cohen-Addad and Jason Li. On the fixed-parameter tractability of capacitated clustering. In Proceedings of the 46th International Colloquiun Automata, Languages, and Programming, volume 132, pages 41:1-41:14, 2019.
Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee, and Jason Li. Tight FPT approximations for k-median and k-means. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, volume 132, pages 42:1-42: 2019.
Vincent Cohen-Addad, Hossein Esfandiari, Vahab S. Mirrokni, and Shyam Narayanan. Improved approximations for Euclidean k-means and k-median, via nested quasi-independent sets. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 1621 1628, 2022.
10

---

Zhen Dai, Yury Makarychev. and Ali Vakilian. Fair representation clustering with several protected classes. In Proceedings of the 5th ACM Conference on Fairness, Accountability, and Transparency, pages 814-823, 2022.
Hu Ding and Jinhui Xu. A unified framework for clustering constrained data without locality property. Algorithmica. 82(4):808 852, 2020.
Zachary Friggstad and Yifeng Zhang. Tight analysis of a multiple-swap heurstic for budgeted red- blue median. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, volume 55, pages 75:1-75:13, 2016.
Mehrdad Ghadiri, Samira Samadi, and Santosh S. Vempala. Socially fair k-means clustering. In Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, pages 438-448, 2021.
Yogesh A. Girdhar and Gregory Dudek. Efficient on-line data summarization using extremum summaries. In Proceeding of the 29th IEEE International Conference on Robotics and Automation, pages 3490-3496, 2012.
Kishen N. Gowda, Thomas W. Pensyl, Aravind Srinivasan, and Khoa Trinh. Improved bi-point rounding algorithms and golden barrier for k-median. In Proceedings of the 34th ACM-SIAM Symposium Discrete Algorithms, pages 987-1011, 2023.
Dishant Goyal and Ragesh Jaiswal. Tight FPT approximation for socially fair clustering. Inf. Process. Lett., 182:106383, 2023,
Anupam Gupta, Robert Krauthgamer, and James R. Lee. Bounded geometries, fractals, and low- distortion embeddings. In Proceeding the 44th Symposium on Foundations of Computer Science, pages 534-543, 2003.
MohammadTaahii Hajiaghayi, Rohit Khandekar, and Guy Kortsarz. Budgeted red-blue median and its generalizations. In Proceedings of the 18th Annual European Symposium Algorithms, volume 6346, pages 314-325, 2010.
MohammadTTaghi Hajiaghayi, Rohit Khandekar, and Guy Kortsarz. Local search algorithms for the red-blue median problem. Algorithmica, 63(4):795-81 814, 2012.
Sariel Har-Peled and Manor Mendel. Fast construction of nets in low-dimensional metrics and their applications. SIAM J. Comput.. 35(5): 148-1184. 2006.
Sèdjro S. Hotegni, Sepideh Mahabadi, and Ali Vakilian. Approximation algorithms for fair range clustering. In Proceedings of the 40th International Conference on Machine Learning, volume 202. pages 13270-13284, 2023.
Lingxiao Huang, Shaofeng H.-C. Jiang, Jianing Lou, and Xuan Wu. Near-optimal coresets for robust clustering, In Proceedings of the 11th International Conference on Learning Representations, 2023.
Ragesh Jaiswal, Amit Kumar, and Sandeep Sen. A simple Da-sampling based PTAS for k-means and other clustering problems. Algorithmica, 70(1):22-46, 2014.
Ragesh Jaiswal, Amit Kumar, and Jatin Yadav. FPT approximation for capacitated sum of radii. In Proceedings of the 15th Innovations in Theoretical Computer Science Conference, volume 287, pages 65:1 65:1-65:21, 2024.
William B. Johnson and Joram Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. Contemp. Math., 26:188 189-209. 1984.
Christopher Jung, Sampath Kannan, and Neil Lutz. Service in your neighborhood: Fairness in center location. In Proceedings of the 1st Symposium on Foundations of Responsible Computing, volume 156, pages 5:1-5:15, 2020.
Matthew Kay, Cynthia Matuszek, and Sean A. Munson. Unequal representation and gender stereo- types in image search results for occupations. Proceedings of the 33rd Annual ACM Conference on Human Factors in Computing Systems, pages 3819-3828, 2015.
11

---

Ravishankar Krishnaswamy, Amit Kumar, Viswanath Nagarajan, Yogish Sabharwal, and Barna Saha. The matroid median problem. Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 11 117-1113, 2011.
Ravishankar Krishnaswamy, Shi Li, and Sai Sandeep. Constant approximation for k-median and k-means with outliers via iterative rounding. In Proceedings of the 50th Annual ACM SIGACT Symposium Theory of Computing, pages 146-659, 2018.
Amit Kumar, Yogish Sabharwal, and Sandeep Sen. Linear-time approximation schemes for clustering problems in any dimensions. J. ACM, 57(2):5:1-5:32, 2010.
Shi Li. A 1.488 approximation algorithm for the uncapacitated facility location problem. In Proceedings of 38th International Colloquium on Automata, Languages and Programming, volume 6756, pages 77-88, 2011.
Sepideh Mahabadi and Ali Vakilian. Individual fairness for k-clustering, In Proceedings of the 37th International Conference on Machine Learning, volume 119, pages 6586-6596, 2020.
Yury Makarychev and Ali Vakilian. Approximation algorithms for socially fair clustering, In Proceedings of the 34th Conference on Learning Theory, volume 134, pages 3246-3264, 2021.
Evi Micha and Nisarg Shah. Proportionally fair clustering revisited. In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, volume 168, pages 85:1- 85:16, 2020.
Mrrni-Francine Moens, Caroline Uyttendaele, and Jos Dumortier. Abstracting of legal cases: The potential of clustering based on the selection of representative objects. J. Am. Soc. Inf. Sci., 50(2): 151-161, 1999.
Shyam Narayanan and Jelani Nelson. Optimal terminal dimensionality reduction Euclidean space. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 1064-1069, 2019.
Maryam Negahbani and Deeparnab Chakrabarty. Better algorithms for individually fair k-clustering. In Proceedings of the 34th Annual Conference Neural Information Processing Systems, pages 13351, 2021.
Chaitanya Swamy. Improved approximation algorithms for matroid and knapsack median problems and applications. In Proceedings of the 17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and the 18th International Workshop on Randomization and Computation, volume 28, pages 403-41 418, 2014.
Suhas Thejaswi, Bruno Ordozgoiti, and Aristides Gionis. Diversity-aware k-median: Clustering with fair center representation. In Proceedings of the 32nd European Conference on Machine Learning and the 25th European Conference on Principles and Practice of Knowledge Discovery in Databases, volume 12976, pages 765-780, 2021.
Suhas Thejaswi, Ameet Gadekar, Bruno Ordozgoiti, and Michal Osadnik. Clustering with fair-center representation: Parameterized approximation algorithms and heuristics. In Proceedings of the 28th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pages 1749-1759, 2022.
Ali Vakilian and Mustafa Yalçiner. Improved approximation algorithms for individually fair clustering. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics, volume 151, pages 8758-8777 2022.
Di Wu, Qilong Feng, and Jianxin Wang. Approximation algorithms for fair k-median problem without fairness violation. Theor Compul. Sci., 985: 14332, 2024.
Zhen Zhang, Junfeng Yang, Limei Liu, Xuesong Xu, Guozhen Rong, and Qilong Feng. Towards theoretical understanding of why local search works for clustering with fair-center representation. In Proceedings of the 38th AAAI Conference on Artificial Intelligence, pages
2024.
12

---

A Proof of Lemma 1
Lemma
Given two real numbers and greater than we have log" S max t0(1)) j.
Proof If 2 Tog logs" then we have log - O(t logt), and thus log' 8 S (0()) If
log
log log log log
then
we have log" <
log ing lng
Thus, Lemma is true.
B Proof of Lemma 2
Lemma 2 Given three points x, y, and in an Euclidean space and a real number y E (0, 1}. we have || =11² s (1 + ")|=== y/1² + (1 + =11².
Proof Triangle inequality implies that || x|1 S = -yll + 11 z|1. and thus we have
|| - 211² - (I|= yl + 11y - =11)²
| v/1² + l1y =||² + 2 1
|| vlll =|l
V7
< r - y11 + l1 211² + - x y11² + >/1y =112.
This completes the proof of Lemma 2
C Proof of Lemma 6
Lemma 6 Given a constant E 00,) and an instance (L, k, F, a. of the fair-range
clustering problem with p {1,2]. |CF n, and C CF C Rd. Algorithm constructs a mapping
sp I8 + _ and instance (t, k, C, 3, P, w) of the weighted fair-range clustering problem in Od d) + (nke-1) time, which satisfy the following properties:
(i) Eeed w(c) = IC,,
(i) w(c) 2 forr each C,
(iii) [C] s n))
(iv) = = ol0) k + log log n). and
(v) E.Ec (c))o((c, [(((f) f E HJ) E - e, c)2pt1 E.Ec (P H. for each H. C F with [H] k.
Proof Algorithm I constructs a mapping şo Rd + Rdd using Lemma in step 1, coreset Ct
along with the corresponding weight function wi C - [1, +00) using Lemma 3 in step 2, and
mapping P2 IRd + a using Lemma 5 in step 3.
We begin by examining the first property of the output of Algorithm T stated in Lemma 6 We have
Σ Ew(c)
-w (c) (((c)=((((())) CE
-ccc= |C],
(I)
cEC
LEct
where the first step follows from the fact that č = (cP2(c) : c c (due to step 4 of Algorithm and w the composite mapping wt o o (due to step Algorithm the second step follows from the fact that Ct is the weighted set constructed by Lemma 3 with (c)()) : c E C} as the input set, and the last step is due to the assumption that the mappings constructed by Lemma Fand Lemma are injective. Equality ( implies that the first property stated in Lemma (6/is true.
The second property stated in Lemma 6 follows directly from the fact that w(c) w (pp((p2))) (c)) for each Ć (as established in step of Algorithm [] and wi is mapping to [1, +o0) (due to Lemma 3).
We now consider the third property stated in Lemma This can be verified by
[C] ct| < (ke log 00) (ke log 0a) log |CU. C (Ke logn)
(2)
13

---

where the first step is due to the fact that č = (p2(c) : E C*} (as established in step 4 of the algorithm) and the assumption that each mapping constructed by Lemma iis injective, the second
step follows from Lemma 3 and the third step is due to the fact that p1 : R -> IRd is the mapping constructed by Lemma with (e,CU) FF) as the input.
Using inequality 2 and the fact that y2 RRd' + Rdd is the mapping constructed by Lemma 5 with (T) as the input, we have
d01) log [c'] S < (01) log(ke logn) = = e00 (log + log logn),
which implies that the fourth property stated in Lemma is true.
Given subset H S F with HH| - k we have
Σ (c)) (vxs)) 74) [1, (1 + e)
Σ
(c.)) kX)
CEC
nECT
S c1 (1+
Σ ('(4((c) ffH)
dEC
S [1- 2)
Σ (c 70).
EEC
where the first step follows from Lemma and the fact that č - (gp((c c E Ct} and (()) =
(p)( for each o F (due to step 4 of Algorithm 1. the second step follows from the fact that
Ct a coreset of {spi (c) : c E C} constructed by Lemma and the last step is due to Lemma 4 This completes the proof of the last property stated in Lemma 6
It remains to show the rumning time of Algorithm I Recall that the algorithm invokes Lemma
with (e, C F),, invokes Lemma 3 with (c, (FI(c) e C), k. p). and invokes Lemma with (c, C
where C C (c) c E CJ C Rdd.. Combining this with inequality ( we can express the running
time of Algorithm|| Mas
(d d + ()) (c--lo log |C (CU ((ct)ate11)00) s Od d) + (nke -1)01
as desired.
D Proof of Lemma 7
Lemma 7 The collection & constructed by Algorithm satisfies the following two properties:
(i) With probability no less than k- there exists collection (Ai, Ak) E A sutisfying I E Ai S Aj for euch E [k*)] and As + 0 for each i E [b]][
(i) Given collection {Ai,... .Ae) A. with A, * @ for each E [k]. and tuple
(fi.... .fa) E A, x A2 X ... X Ag, we have Hi E [b] :tt +(f))} E [a., 3,] for each 1 1 [0).
Proof Algorithm enumerates all possible values of A for each i E [k=*] and all possible values of L, for each i [k: k.*). Consequently, the k sets Ai.... Aj,,CL-
Ls are guaranteed be captured by the algorithm. Observe that Algorithm alssociiatss each facility ʃ with a random integer sivii e [k] holds with probability - When this equality is satisfied, and the k sets ...... A L1.
m(f) E [k]. It can be shown that equality n(f?)
La are provided, the algorithm able to construct a set A, satisfying f A, S. A for each i E [k=*] by extracting the facilities E A with rf)) = i in step 14, and find a facility f E L; with rf()) = to construct a singleton set Ai S L. for each E [<]][]]] in step 17. Thus, the first property stated in Lemma 7 is true.
Now we consider the second property. Given a collection (A,,..., Au) E A with A, + 0 for each i [k] and tuple (Ji,... Sb) Ai A2 x... x As. the fact that facilities in different sets are associated with distinct integers implies that {/1, ... } is a distinct set. Combining this with the decision condition employed in step 6 of Algorithm we have
Hi [k] t E 7 (ff))] i[i e [k] :tt D.Yl [ar,
for each 1 E [e] where Dj,... Dr are the sets of demographic labels used for constructing This completes the proof of Lemma 7
}. -
14

---

E Proof of Lemma 9
The following event occurs with probability no less than 1 e Algorithm yields feasible H to I satisfying Ence w(c) H!) < (1+4 if p 1 and Ence w(c) (c, H
Lemma 9
(1 + +9-))opp pf =
Proof The second property stated in Lemma immediately implies that all candidate solutions constructed by Algorithm 3 are feasible solutions to I. It remains to consider the approximation ratio of the algorithm. Given that Algorithm 3 iteratively invokes Algorithm 2 k* times construct a collection A, the probability that there exists an element {AA1. ... .Ax) E A. satisfying the first
property stated in Lemma 7 is at least (1 - k & we assume that the collection A indeed contains such an element {A1,-.. ... ).), and let S be the subset of A, constructed by Algorithm in step 8 step 10 for each E [A]]
e For the purpose our analysis,
We consider an integer i E [k*]. Lemma 7 indicates that
S: A, {
Ac] 1. For the case where |Ai:] 1, S. is ma e||o - yll-net of Ai. In this scenario, can be concluded that
8 (ff S el max a.yEA;
|| 3/1º
< 2p max ||ʃ cill SEA:
< 2pc max (1 + c)lfff cill. k
n
S 2pe max + +)]lf aill. opt];
(4)
where the first step follows from the fact that S E A: (due to Lemma 7 and the definition of nets,
the second step follows from triangle inequality (for p = 1) and Lemma 2 (for p = 2, with Y = 1), the third step follows from the fact that integer j E (..... Ic log
satisfies A, C Ai, (due to Lemma 7. along with the fact that each j E [[c_]] and {z, y) S (i, satisfy ||x- - - < (1 + e)lly call l and each f E (i, 0) satisfies |[f - cill S cd maxax n (due to the definitions of A" (i,j) and (i, 0)), and the last step follows from the definition of 6 and the fact that (cc) 2 1 for each c E è (due to Lemma 6)
Let HI' be the set of candidate solution constructed using the Cartesian product S₁ S2 ................................ x Sy in step 11 of Algorithm|3 3 Equality (3) and inequality (4) suggest the existence of candidate solution {fi,... fk] H'' satisfying
llfi - fill 2pe". max + +ellfft call. c opt n
(5)
for each E [k*]. Thus, can be shown that
w(c)llf: MP
Σ
Σ
w(c)lli
GEC
ecc;
2pe
w(c)
cill, optt
n
i=1 oEct
k*
w(c) (1++))lff - -- || + c opt
< 2pc
iml
cEC:
d
22 E)
Σ
w(c)llft c:ll + 2t opt
1=1 ceč:
< <2pe 11++6
w(c)llff c|lp + + opt
15

---

(1 + e)opt + 2pe opt 4pc
lopt
(6)
where the first step due to the fact that Ō for each [k*]] the second step is due to
inequality (5). the fourth step follows from the fact that Σx=1 Eceo; w(c) Eeec w(c) |C| < n
(due to 6e the fifth step is due to the definition of C₁. the sixth step is due to the definition of Cj and the last step follows from the fact that (0, 0.5). Consequently, for the case where P 2. we have
Σ (e(c))"(e, "............................... .f,)), GEC
Σ
Σ
(fi, fx.)
i=1 nEC
wl(c)le- -iil
oEC;
w(c)
(1+ (1+ I1s. - salP))
1=1 rEC
= (1 Vppt + +1+
1
Σ Σ
w(c)llst - fill
Vc
:= cEE
V+ 4(1+ ve
)pee)
opt
< (1 //C)opt,
where the third step is due to Lemma (with = V the fourth step follows from the definition of čr the fifth step follows from inequality (6). and the last step is due to the fact that E (0, 0.5).
Replacing Lemma] 2 used in the third step of inequality (7) with triangle inequality, we get
Σ (c (f,, fia)) = cEc
w(c) (lle 1/1 + I1ft - f(ll
cEC;
opt Σ cE
w(c)llff fill"
< (1 + 4e)opt
(8)
for the case where p=
Using inequality 7 and inequality (8 along with the fact that Algorithm 3 returns the candidate
solution with the minimum cost, we complete the proof of Lemma
F Proof of Lemma
Lemma 10 Algorithm
3 runs in more than 2 -1)() tke, 0(1) time.
Proof Let H be the set candidate solutions constructed by Algorithm 3 and let the collection formed by iteratively invoking Algorithm 2 1* times. Observe that Algorithm 2 enumerates all possible values of k.,, sets (1, (k",", log (o)) and {Lx*41, Lx). Additionally, it enumerates 2 ]|] U [0)]* to determine the set (Air... , Analyzing the possible values of these parameters yields
..,c)) 8faxx and {Li..... ,L) to guess the
A < 2 1112 Pog + 1)a²
s 2 (ke pkk (k))
< 2d (ke -1)0kin 0(1)
(9)
16

---

where the second step follows from the fact that = (ke-) log n ( (due to Lemma 6 and [F < n. and the third step follows from Lemma [ (with
and k).
Let (A1: ......... A E A. be the collection considered in one of the iterations of steps 6-12 of Algorithm Let S1, ... S& be the subsets constructed in step 8 step 10 and H' be the set of candidate solutions constructed in step 11 during this iteration. For each i E [k] with |Ag] > 1, S; is a maxa.yEA. e||> -eet of A,, which is constructed based on the maximum distance between the facilities from A, in step 10. Lemma implies that constructing these nets takes no more than
Σ A ow 20(0) F1000 < 20l0) o00
(10)
suggests time. Moreover, the upper bound the size of net exhibited in Lemma Suggessu that
S S c-d
(11)
for each [k]. Inequality 11I) leads to
S S E
i=1
and thus we have
Se kdd |.].
(12)
Given the set H of candidate solutions, Algorithm takes Ccdck H time to identify the solution with the minimum cost. Combining this with the time required for constructing nets in each iteration exhibited in inequality (10). we know that the running time of Algorithm 3 is upper-bounded by
20th o| + |2] [ S |A (1((0)))) 0(1) + c kd ((d)
< 2 -0(k)) 0(1) (K) (1(())
S n (kc 100A0)) (A: log n) ( (2-))
2 - 0(1),
where the first step follows from inequality 12). the second step follows from the fact that [C] s (ke-1 log n)) (due to Lemma and inequality (9) the third step follows from the fact that d ((1) (log k + log log n) (due Lemma 3). and the last step due Lemma (with
and (ke 1)0(1)) This completes the proof of Lemma 10
G Proof of Theorem
Theorem Given an instance (e, F, ā. P. of fair-range clustering with CUJ C Rd and E {1,2} along with real number E (0, there is randomized (1 + -appproxxinttoon algorithm running in (d d) + (kke 2 0(1) time, where n ICU.F.
Proof Let 76 be the solution to I returned by Algorithm and let Ht be the solution to I constructed in step 2 of Algorithm 4 Since each facility in H shares the same of demographic labels as its corresponding image in Rd follows that H a feasible solution to I. Let H.* be an optimal solution to I and H be an optimal solution to Z.
The optimality of H for I and Lemma impply that
Σ (c HC) < Σ (())))(c.(()())) H*})
CEC
< (1 + c)apt1 Σ (c(c, H²).
(13)
3EC
17

---

For the case where p 1, we can derive that inequality
E Ht
-
Σ (c,)
1
oEC
CEC
1 + 4e Σ
wc()) H²)
1
rEC
1 + 4e
+ +e++ e)2tt1
Σ 8c H*)
39c)
(c, H*)
(14)
holds with probability no less than - e where the first step is due to the fact that 7e = {fp(f)
the third step is due to inequality (13 and the last step follows from the fact that E (0,0.5, 0.5). Similarly, we can conclude that inequality
f E H } and Lemma the second step follows from Lemma 9
Σ (c, H²) EEC
1 Σ
(cc)) H!)
1-c
oEC
+ 9
Σ (c,
1-e
1 + 9VC
(1 + c))pt1
Σ (c))
1-c
AEC
83VE))))
(c,
(15)
aEC
holds with the same probability when 2, where the second step is due to Lemma 9
Using inequality (14) and inequality (15). know that Algorithm 4 is randomized (1 + 39c) approximation algorithm for the FkMed problem and a (1 + ( approxxmiiiiiio algorithm for the FKMeans problem. Moreover, Lemma 6 and Lemma 10 imply that this algorithm runs in
Od d) + the time.
Given a constant E 1), e problem, then the argument above implies the existence of (1 + approxxmaaii algorithms with running time (d d) + 2kke + k 0(1) for both problems, as desired.
for the Fkledd problem and ( ) for the FkMeans
18

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The paper's contributions and scope have been accurately claimed in the abstract and introduction.
Justification:
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: The limitation of the algorithms in the paper is that they consider l: and as fixed parameters, which has been clearly discussed the paper.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: All the proofs are clearly provided.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: The paper does not include experiments.
5. Open access to data and code
Question: Does the paper provide open the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: The paper does not include experiments.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
9. Code Of Ethics
19

---

Question: Does the research conducted in the paper conform, in every respect. with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: The research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics.
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The potential societal impacts and negative societal impacts are discussed in the last section of the paper.
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses such risks.
12. Licenses for existing assets
Question:
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects. 15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
20


Reviews:
[{"review_id": "FFQYPpKyq1", "reviewer": "Reviewer_nDwN", "summary": "The paper deals with the problem of fair-range clustering in Euclidean metric spaces. In fair-range clustering, one is given a set of clients and a set of possible facilities. Every facility is associated with a subset of $\\ell$ many classes. The goal is to pick up to $k$ many facilities such that a given clustering objective is minimized with respect to the chosen facilities as centers under the side constraint that the number of facilities that are associated with a certain class lies $i$ within a given interval $[\\alpha_i,\\beta_i]$, for all $i\\leq \\ell$. \nThe clustering objectives considered here are the $k$-Median and the $k$-Means objective.\nThe authors propose FPT $(1+\\epsilon)$-approximations for both problems with parameters $k$ and $\\ell$.\nTheir approach essentially works by first mapping the input to an Euclidean space of lower dimension and computing a coreset. For such a low-dimensional weighted instance, they give an algorithm that computes a near-optimal approximation on the modified instance. In the end, they translate the solution back to a solution for the original instance by returning the pre-image of the injective mapping from the transformation step.", "questions": "- line 9 of Algorithm 2 assigns every facility an integer at random. This makes your algorithm a randomized algorithm and influences the result of Lemma 9. As Lemma 9 is used in the proof of Theorem 1, Theorem 1 should also mention that this guarantee holds *with high probability*. Please clarify.\n- What is the motivation for using first the original Lindenstrauss transform and then the stronger version in the second step? Why do you not need the stronger transform in the first step?", "limitations": "Yes, the authors clearly state the limitations (fixed-parameter tractability with parameters $k$ and $\\ell$, restriction to Euclidean metric spaces) in the abstract. In Section 6, they also state considerations to make when using their results for practical applications.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "This is a well-written and clear paper with a good contribution. There already existed optimal FPT($k$,$\\ell$)-algorithms for the two considered problems matching known lower bounds. In this paper, the authors manage to break the barriers for general metric spaces when restricting to Euclidean metric spaces by giving near-optimal $(1+O(\\epsilon))$-approximation algorithms for the Euclidean setting.", "weaknesses": "Apart from the Questions mentioned later, I only have minor comments. I am willing to increase my score to \"accept\" when addressing the questions.\n\n_Comments to the authors:_\n- please provide a citation for the results mentioned in the abstract (lines 9-10)\n- please define $\\tau$ and $\\ell$ in the preliminaries\n- are Lemma 1 and Lemma 2 needed somewhere in the main body of the paper? Otherwise, they could be transferred to the appendix\n- figure 1: please provide an explanation of the different symbols (small circles = clients, squares = facilities?)\n- l. 171: what do you mean by \"distance parameter\"? \n- why is the upper bound stated in equation (2) meaningful? How does it help in bounding $\\delta_{\\max}^{\\rho}$ if it contains $\\delta_{\\max}^{\\rho}$?\n- how are the annuli guessed if the possible radii depend on the maximal distance within an optimal solution in lines 229,230? When looking at the proof of Lemma 8, it becomes obvious that the value of $\\delta_{\\max}^{\\rho}$ is guessed. Please also provide this information in the text.\n- In general, is a bit difficult to recognize which are the parts that are guessed in Algorithm 2. If I understood correctly, the rings $A_i$ are guessed (which includes guessing the leader $c_i$, the radius of the annulus, which is based on guessing $\\delta_{\\max}^{\\rho}$, and the set $L_i$), the color coding is done randomly, and the feasible solution of lowest cost is again guessed (lines 15-16 in Algorithm 2). It would be helpful to specifically state which things have to be guessed in the text.\n- It is not specified how the values are chosen randomly in line 9 of Algorithm 2, resp. lines 249-253 (Uniformly at random?). Please make this more formal.\n- it does not become entirely clear to me how the feasible solution is chosen in lines 15-16 in Algorithm 2. Are you iterating over *all* possible subsets of $S$ and only then check whether the subset contains at most $k$ elements? This seems a bit wasteful. Why would it not be enough to choose one facility from every ring? It would be helpful if you write this part in lines 258-259 a bit clearer. \n\n\n\n_Language, Typos & Layout_\n- 112: \"number\" -> \"numbers\"\n- 216: I guess that \"see Appendix [...]\" belongs in the next line\n- 223: \"denotes\" -> \"denote\"\n- 229, 230: Why do you use $\\|f-c_i\\|^{\\rho}$ instead of $\\delta^{\\rho}(f,c_i)$ here?\n- it might increase readability if you restate Theorem 1 where it is proven", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful comments. We summarize our responses in the following.\n\n**Q1: Regarding the randomness of Algorithm 2.**\n\nResponse: Thanks for pointing this out. The probability that Algorithm 2 yields the desired $(1+\\varepsilon)$-approximation solution is the same as the probability that inequalities in Lemma 9 hold. In our revised version, we will modify Theorem 1 and its proof to clarify the randomness of our algorithm and the associated success probability.\n\n**Q2: What is the motivation for using first the original Lindenstrauss transform and then the stronger version in the second step? Why do you not need the stronger transform in the first step?**\n\nResponse: The motivation for using the original transform in the first step is primarily driven by computational efficiency: Although the stronger transform guarantees that the distance similarity between the original space and its low-dimensional mapping is preserved over a broader range, it involves semidefinite programming and has a higher time complexity.\n\nIn the first step, we use the union of clients and facilities as the input for the dimension-reduction method, aiming to map the instance to a space whose dimension is independent of $d$ (the dimension of the original space). This mapping needs to preserve the distance between each pair of points in the input set, without considering the points outside this set. Both the original and stronger transforms can achieve this goal. However, we choose the original transform because it has a lower time complexity.\n\nIn the second step, we use a coreset of size $(k\\log n)^{O(1)}$ as the input for the dimension-reduction method, aiming to map the instance to the desired $O(\\log k+\\log\\log n)$-dimensional space. Here, we need to preserve the distance between any point in the coreset and any facility (outside the coreset). Due to the requirement of preserving distances over a broader range than in the first step, we choose the stronger transform in this step.\n\nWe will elaborate on the above intuition in our revised version to enhance the understanding of Algorithm 1.\n\n**Q3: Regarding the presentation.**\n\nResponse: We thank the reviewer for pointing out the typos and issues with the presentation. We will carefully correct these in our revised version. We apologize for being unable to response to each typo and presentation issue individually due to the space constraint.\n\n**Q4: Line 171: what do you mean by ''distance parameter''?**\n\nResponse: The distance parameter denotes the parameter ''$\\lambda$'' in Definition 2 and Lemma 6. As this parameter decreases, the constructed net becomes larger, causing our algorithm to take more time, but the opened facilities selected from the net more closely approximate the optimal ones. We will make this clear in the revised version. \n\n**Q5: Why is the upper bound stated in equation (2) meaningful? How does it help in bounding $\\delta^\\rho_{\\max}$ if it contains $\\delta^\\rho_{\\max}$?**\n\nResponse: We construct annuli centered at the leaders. Since the left-hand side of equation (2) is the maximum radius of the annuli (recall that the distance from each facility in the annulus $A(i,j)$ to the leader $c_i$ is at most $\\epsilon(1+\\epsilon)^{j}\\delta^\\rho_{\\max}n^{-1}$ and $j\\in\\\\{0,\\cdots,\\lceil\\epsilon^{-2}\\log n\\rceil\\\\}$), and the right-hand side denotes the maximum distance among the facilities in $\\tilde{H}^*$ to their corresponding leaders, equation (2) implies that each facility in $\\tilde{H}^*$ is involved in one of the annuli. This suggests that enumerating over $j\\in\\\\{0,\\cdots,\\lceil\\epsilon^{-2}\\log n\\rceil\\\\}$ to identify an annulus $A(i,j)$ that contains the optimal opened facility $f_i^*$ is feasible. We will clarify this in the revised version.\n\n**Q6: How are the annuli guessed if the possible radii depend on the maximal distance within an optimal solution in lines 229, 230? When looking at the proof of Lemma 8, it becomes obvious that the value of $\\delta^\\rho_{\\max}$ is guessed. Please also provide this information in the text.**\n\nResponse: We guess the value of $\\delta^\\rho_{\\max}$ by examining the distance between each pair of client and facility. We need to enumerate $n^{O(1)}$ items in this process, which introduces a $n^{O(1)}$ multiplicative overhead in the running time of the algorithm. We will make this clear in the revised version.\n\n**Q7: Regarding the parts that are guessed in Algorithm 2.**\n\nResponse: Algorithm 2 guesses the rings $A_i$ by enumerating the possible values of $c_i$, $L_i$, $\\delta^\\rho_{\\max}$, and the integer $j\\in\\\\{0,\\cdots,\\lceil\\epsilon^{-2}\\log n\\rceil\\\\}$ satisfying $f^*_i\\in A(i,j)$, iteratively performs color coding and guesses a successful iteration (which exists with constant probability), and selects the solution with lowest cost from the candidate set. We will clarify this in the description of Algorithm 2 in the revised version. Moreover, we will include an algorithm that formally describes how to construct the set $\\mathbb{A}$ of possible values for $\\\\{A_1, \\cdots, A_k\\\\}$, rather than providing it implicitly in the proof of Lemma 8.\n\n**Q8: It is not specified how the values are chosen randomly in line 9 of Algorithm 2, resp. lines 249-253 (Uniformly at random?). Please make this more formal.**\n\nResponse: Sorry for the informal presentation. The color of each facility is chosen uniformly at random in step 7. We will make corresponding modifications in the revised version.\n\n**Q9: Regarding the selection of the feasible solution in lines 15-16 of Algorithm 2.**\n\nResponse: Indeed, merging the sets of candidate opened facilities selected from the $k$ rings and enumerating the subsets of the union $S$ to find feasible solutions is unnecessary. It is sufficient to separately construct $k$ sets of candidates based on the rings and select one opened facility from each set. We will make corresponding modifications in Algorithm 2 and its description.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "aiujmTYFcu", "reviewer": "Reviewer_c25h", "summary": "- This paper studies fair range clustering, which aims to ensure that cluster centers are not dominated by specific demographic groups.\n- It focuses on fair range clustering using the 1-norm and 2-norm distance metrics.\n- The paper proposes an algorithm with three internal steps: (i) data reduction to low-dimensional space, (ii) obtaining fair centers in the low-dimensional space, and (iii) transforming the centers back to the original high-dimensional space.\n- The authors theoretically demonstrate that the algorithm can be computed in Fixed Parameter Tractable (FPT) time.", "questions": "1. What is the intuitive definition of “core set”?\n2. What is the role of the core set in data reduction? \n3. The authors mention that Thejaswi et al. [2022] showed limits of approximation order in a general metric space (lines 73-77). How is the approximation order improved when considering Euclidean space rather than a general metric space?\n4. Is $\\tilde{\\mathcal{S}^*}$ in line 504 defined? If not, what is its definition?", "limitations": "1. It is not confirmed that the proposed algorithm can be applied to real scenarios.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The problem considered in this paper allows each center (facility) to include multiple demographics, whereas a previous work considers a single demographic label for each center.\n- The proposed algorithm can be computed in FPT-time.\n- The algorithm is theoretically applicable to high-dimensional data.", "weaknesses": "1. The writing and presentation are complex, making it difficult for non-experts to follow. It assumes readers are very familiar with fair range clustering.\n2. The paper focuses too much on techniques used to derive the algorithms, lacking intuitive explanations about how the algorithm works.\n3. The introduction should better justify the necessity of fair range clustering. It should include related works on (conventional) fair clustering [A, B, C] and their key differences to highlight the significance of fair \"range\" clustering.\n4. The data reduction mechanism lacks novelty, appearing to be a direct consequence of combining Lemmas 3, 4, and 5, which were not developed by the authors.\n5. The link mapping $\\phi$ between low-dimensional space and high-dimensional space, which is a key component of the proposed algorithm, is theoretically valid (through Lemmas 4 and 5), but practical construction methods are not discussed.\n6. Numerical analysis is missing. Given existing works on fair clustering [A, B, C] or fair range clustering [D] with numerical results on real data, appropriate experiments are necessary.\n7. (Minor) line 451: second -> third, line 454 : third -> fourth\n\n[A] Fair Clustering Through Fairlets\nhttps://dl.acm.org/doi/pdf/10.5555/3295222.3295256 \n\n[B] Fair Algorithms for Clustering\nhttps://proceedings.neurips.cc/paper_files/paper/2019/file/fc192b0c0d270dbf41870a63a8c76c2f-Paper.pdf\n\n[C] Variational Fair Clustering\nhttps://arxiv.org/abs/1906.08207 \n\n[D] Fair k-Center Clustering for Data Summarization\nhttps://proceedings.mlr.press/v97/kleindessner19a/kleindessner19a.pdf", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful comments. We summarize our responses in the following.\n\n**Q1: What is the intuitive definition of ''core set''?**\n\nResponse: Thanks for the question. A ''core set'' is a small subset of the client set. For any feasible solution, its costs on the original instance and reduced instance (where the client set is replaced by the core set) are approximately the same. Constructing a core set and using it to reduce the instance can significantly enhance computational efficiency while ensuring that the solutions closely match those obtained from the full client set. We will clarify this in our revised version.\n\n**Q2: What is the role of the core set in data reduction?**\n\nResponse: In data reduction, constructing a core set helps to reduce the size of the client set: We replace the client set with a smaller core set. This has the following two effects.\n\n(1) When invoking Lemma 5 with the client set as input, we can map the instance into a low-dimensional space without significantly altering the distance between each pair of client and facility. Here, the dimension is logarithmically related to the number of clients. By reducing the number of clients using a core set, we can significantly lower the dimension.\n\n(2) We construct the solution based on the ''leaders'' (i.e., the clients closest to the facilities opened in an optimal solution) within the client set. Replacing the original client set with the core set allows us to identify these leaders in FPT time.\n\nWe will clarify the role of the core set in our revised version.\n\n**Q3: The authors mention that Thejaswi et al. [2022] showed limits of approximation order in a general metric space (lines 73-77). How is the approximation order improved when considering Euclidean space rather than a general metric space?**\n\nResponse: The properties of the Euclidean metric allow us to carefully partition the space. We can thus restrict the solution search space to a more refined range, and thereby break through the lower bound on the approximation ratio that applies to general metric spaces. Specifically, our algorithm partitions the search space into smaller cells, ensuring that each facility opened in an optimum is close to the center point of the cell it belongs to. Consequently, we can identify a nearly-optimal solution by enumerating the subsets of center points of the cells. We will describe this idea in Section 1.1 of the revised version.\n\n**Q4: Is $\\tilde{\\mathcal{S}}^{*}$ in line 504 defined? If not, what is its definition?**\n\nResponse: The notation $\\tilde{\\mathcal{S}}^*$ should be $\\tilde{\\mathcal{H}}^*$, which denotes an optimal solution to $\\tilde{\\mathcal{I}}$. Sorry for the typo.\n\n**Q5: Regarding the presentation.**\n\nResponse: Thanks for pointing out the issues with the presentation. We apologize for being unable to response to each issue individually due to the space constraint. We will carefully correct the typos and reorganize the content in the revised version. First, we will clarify the intuitive ideas of our algorithms, including the roles of Lemmata 3, 4, and 5, as well as the partitioning of the solution search space. Second, we will add related work on conventional fair clustering, and underline the significance of fair range clustering by highlighting its important roles in applications where the centers are required to fairly represent the demographic groups.\n\n**Q6: The data reduction mechanism lacks novelty, appearing to be a direct consequence of combining Lemmas 3, 4, and 5, which were not developed by the authors.**\n\nResponse: JL-transform (Lemmas 4 and 5) has been widely utilized in clustering problems. However, given that most previous works directly use this transform to construct an $O(\\log n)$-dimensional space, we think it is somewhat unexpected that this transform, combined with a coreset-construction method (Lemma 3), yields an $O(\\log k+\\log\\log n)$-dimensional space. This allows us to partition the solution search space into sufficiently small cells. Furthermore, given that there are algorithms for constructing coresets for the fair clustering problem where the fairness constraint is imposed on the clients [1], our idea for data reduction has the potential of being applicable to this problem as well. \n\n[1] Sayan Bandyapadhyay, Fedor V. Fomin, and Kirill Simonov. On Coresets for Fair Clustering in Metric and Euclidean Spaces and Their Applications. In Proc. of ICALP 2021: 23:1-23:15\n\n**Q7: Regarding the practicality of the mapping $\\phi$.**\n\nResponse: The coreset-construction algorithm in Lemma 3 runs in linear time, and one can easily trade off the size of the constructed coreset against its approximation guarantee. Moreover, it is built upon random sampling and is simple to implement. Thus, we believe that our coreset-based adaption of JL-transform is quite practical. \n\n**Q8: Regarding the nonexistence of experiments.**\n\nResponse: In line with recent advancements in hardness and approximability of fair range clustering [2,3,4], our research focuses on theoretical aspects, breaking through the lower bound in general metric spaces and providing the first FPT approximation scheme under the Euclidean metric. Given the widespread consideration of Euclidean data in fair range clustering problems, we believe that gaining such a new understanding of the problem's approximability in Euclidean spaces is of intrinsic value.\n\n[2] Suhas Thejaswi, Ameet Gadekar, Bruno Ordozgoiti, and Aristides Gionis. Diversity-Aware Clustering: Computational Complexity and Approximation Algorithms. CoRR abs/2401.05502, 2024\n\n[3] Zhen Zhang, Junfeng Yang, Limei Liu, Xuesong Xu, Guozhen Rong, and Qilong Feng. Towards a Theoretical Understanding of Why Local Search Works for Clustering with Fair-Center Representation. In Proc. of AAAI 2024: 16953-16960\n\n[4] Sèdjro Salomon Hotegni, Sepideh Mahabadi, and Ali Vakilian.\nApproximation Algorithms for Fair Range Clustering. In Proc. of ICML 2023: 13270-13284", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fBt3hqpZwc", "reviewer": "Reviewer_py4M", "summary": "The paper presents fixed-parameter approximation schemes for the fair-range k-median and k-means problems in Euclidean spaces, parameterized by both the number of facilities and labels. The results improve on existing results, which could only achieve constant-ratio approximation. The main technique used is a data-reduction technique to reduce the dimensionality, combined with an algorithm for low-dimensional spaces.", "questions": "Did you consider any other notions of fairness, based on other constraints (e.g., related to clients)?", "limitations": "Lack of experimental work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper presents an FPT APX-scheme for very important clustering problems.\n2. The approximation results improve on the current best results.\n3. The results are theoretically solid and technical.", "weaknesses": "1. The techniques are not novel. \n2. The results are purely theoretical, with no experimental results provided.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful comments. We summarize our responses in the following.\n\n**Q1: Did you consider any other notions of fairness, based on other constraints (e.g., related to clients)?**\n\nResponse: Thanks for the question. For the fair clustering problem where clients are partitioned into different demographic groups and the proportion of each group in each cluster is constrained, it is known that a variant of the algorithm stated in Lemma 3 yields small-size coresets [1]. By replacing the algorithm in Lemma 3 with this variant, one can generalize our data-reduction method (Algorithm 1) to address the clustering problem with the fairness constraint imposed on clients. Consequently, we believe that the ideas in the paper have the potential of being applicable to the client-constrained case. We will add this intuition and related work on the client-constrained fair clustering problem in the revised version.\n\n[1] Sayan Bandyapadhyay, Fedor V. Fomin, and Kirill Simonov. On Coresets for Fair Clustering in Metric and Euclidean Spaces and Their Applications. In Proc. of ICALP 2021: 23:1-23:15\n\n**Q2: Regarding the novelty of the work.**\n\nResponse: Some aspects of the work are built upon existing methods, such as Johnson-Lindenstrauss transform and the construction of coresets and nets. However, leveraging these well-known techniques to improve upon the previously known constant-factor approximation ratios in Euclidean spaces is non-trivial. To achieve this goal, we give a novel approach for exploring the properties of the Euclidean metric in the context of the fair-range clustering problem. This includes partitioning the solution search space into small cells and carefully balancing the number of cells (which affects the running time) with the distance from each facility opened in an optimum to the center point of the cell it belongs to (which affects the approximation ratio). In our revised version, we will make the ideas that distinguish the work clearer in the introduction.\n\n**Q3: Regarding the nonexistence of experimental work.**\n\nResponse: Our research focuses on the theoretical aspect of the fair-range clustering problem, demonstrating an upper bound of $1+\\varepsilon$ on the parameterized approximation ratio in Euclidean spaces. Considering the significant attention received by the hardness and approximability of the problem [2,3,4], we believe that gaining this new understanding of its approximability is of independent interest.\n\n[2] Suhas Thejaswi, Ameet Gadekar, Bruno Ordozgoiti, and Aristides Gionis.\nDiversity-Aware Clustering: Computational Complexity and Approximation Algorithms. CoRR abs/2401.05502, 2024\n\n[3] Zhen Zhang, Junfeng Yang, Limei Liu, Xuesong Xu, Guozhen Rong, and Qilong Feng. Towards a Theoretical Understanding of Why Local Search Works for Clustering with Fair-Center Representation. In Proc. of AAAI 2024: 16953-16960\n\n[4] Sèdjro Salomon Hotegni, Sepideh Mahabadi, and Ali Vakilian.\nApproximation Algorithms for Fair Range Clustering. In Proc. of ICML 2023: 13270-13284", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9iTqcOZz7B", "reviewer": "Reviewer_HhQt", "summary": "The authors study the fair range clustering problem, where facilities are associated with multiple demographic labels, forming intersecting groups. They impose both lower and upper bounds on the number of cluster centers chosen from each label. For both $k$-median and $k$-means clustering objectives, they present a $1 + \\epsilon$ approximation algorithm when the underlying metric space is Euclidean.\n\nThe key contribution of this work is leveraging the properties of Euclidean metric spaces to improve approximation ratios while maintaining similar running times as for general metric spaces, specifically fixed-parameter tractable (FPT) in parameters $k$ and $\\ell$. \n\nThe authors make use of the techniques and results that are known the literature, but it is still challenging to stitch the pieces together to obtain a solution and formally prove all the claims, which the authors have successfully managed to do. I have verified proofs in sufficient detail and cannot find anything wrong or incorrect. It is possible that I may have missed something. \n\nThe writing can be simplified by clearly explaining the figures and explicitly stating that Figure 2 applies only to clients. It took me some time to realize that the facility set does not undergo the same transformation, as the coreset applies only to clients. Also it was difficult to understand precisely what the authors refer to as the annular region in Figure 1a (this was only clear after reading Section 4.2, and discretisation of distances).\n\nIn a nutshell, the approach works by first reducing the high-dimensional space to lower-dimensions, present $1 + \\epsilon)$ FPT algorithm in lower-dimensions and show that this solution translates to a $ 1 + O(\\epsilon)$ FPT approximation in higher dimensions.", "questions": "The extension from considering only lower bound requirements to including both lower and upper bound requirements is straightforward in the work of Thejaswi et al. 2022. In their work, see Lemma~5.2, which exhaustively lists/enumerates all feasible constraint patterns satisfying the lower bound requirements, and this can be extended to enumerate feasible constrained patterns that satisfy both lower and upper bound requirements. Consequently, all algorithmic findings of diversity-aware clustering (with lower bound requirements) would extend from this adaptation to fair-range clustering (with lower and upper bound requirements), although the authors themselves do not explicitly assert this claim, the extension is immediate. Do you agree with this, or do you hold a different viewpoint? \n\nLine 52-54: This statement is not accurate. The reduction presented by Thejaswi et al. (2021) from diversity-aware $k$-median to matroid median problem shows that any algorithm for matroid median can effectively handle the scenario with disjoint facility groups. Consequently, this reduction yields a $7.081 + \\epsilon$ approximation for the disjoint facility groups case, as further detailed in Theorem~7.1 of Thejaswi et al. (2024) preprint on ArXiv this also yields a FPT($k$) algorithm with 1 + 2 e^{-1} approximation. Do you hold a different viewpoint on this?\n\nFigure 1(a): The caption does not clearly explain the significance of the two circles around the client. It would be beneficial to explicitly specify these details. Are these circles representing the distance defined by the authors in Lines 228-229 on Page 6 (as a consequence of discretisation of distances)? please clarify.", "limitations": "In the broader impact section authors have briefly mentioned the potential social impact of their work.", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This work has significant theoretical contributions, offering new insights into a known difficult clustering problem variant, where earlier works have extensively investigated and established the computational complexity of the problem.", "weaknesses": "Similar to earlier work by Thejaswi et al. (2022), the presented FPT algorithms may not scale practically, given that the exponential factors are large. In theory, dimension reduction and coreset constructions are expected to introduce a minimal $\\epsilon$ factor of distortion in distances. However, in practice, creating smaller-sized coresets often requires a larger $\\epsilon$, which limits the practical scalability of algorithms. Also the achieved approximation factors in practical applications may be significantly larger than the theoretical claims. Even though the theoretical contributions are good, I would suggest that the authors put an effort to perform (at least some) experimental evaluations when submitting to an applied conference such as NeurIPS.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful comments. We summarize our responses in the following.\n\n**Q1: Regarding the extension from diversity-aware clustering to fair-range clustering.**\n\nResponse: Thanks for pointing this out. Following your guidance, we found that when $k$ and $\\ell$ (i.e., the maximal number of opened facilities and the number of demographic groups) are fixed parameters, it is straightforward to extend an algorithm for diversity-aware clustering to fair-range clustering, based on the method for enumerating feasible constraint patterns given in the work of Thejaswi et al. (2022). We will clarify this in the revised version.\n\n**Q2: Regarding the reduction to the matroid median problem.**\n\nResponse: Sorry for the incomplete description of related work. Thejaswi et al. (2021) demonstrated that the diversity-aware clustering problem can be reduced to the matroid clustering problem when the demographic groups are disjoint and the sum of lower bounds associated with the groups equals $k$. It was also indicated that this reduction can be extended to the fair-range clustering problem with an $O(k^{\\ell-1})$ multiplicative overhead in the running times of the algorithms. We will clarify this reduction and the corresponding approximation results in the part of related work in the revised version.\n\n**Q3: Figure 1(a): The caption does not clearly explain the significance of the two circles around the client. It would be beneficial to explicitly specify these details. Are these circles representing the distance defined by the authors in Lines 228-229 on Page 6 (as a consequence of discretisation of distances)? Please clarify.**\n\nResponse: In Lines 228-229, we introduce a set of annuli centered at $c_i$ by discretizing the distances from the facilities to $c_i$. Each annulus is defined such that its outer radius is $1+\\varepsilon$ times its inner radius. The circles shown in Figure 1(a) represent the outer and inner circles of the annulus involving $f^*_i$ (i.e., the facility corresponding to the leader $c_i$). This will be clarified in the revised version.\n\n**Q4: Regarding the explanation of Figure 2.**\n\nResponse: Sorry for the unclear presentation. In the revised version, we will include a description of the process illustrated in Figure 2. Additionally, we will enhance the clarity of the data-reduction algorithm by explaining the roles of JL-transform and coreset construction.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We greatly appreciate the reviewers for the in-depth reviews, which have significantly helped us in improving our work. Below, we provide detailed responses to the comments.

Meta-review: Fair-range clustering is a natural clustering problem that has gained attention in recent years. All reviewers agree that this submission makes significant theoretical progress on the approximability of this problem by deriving an FPT approximation scheme for the Euclidean case despite existing hardness results for general metrics. There has been a detailed discussion and the authors addressed all questions raised by the reviewers. The only weakness is the lack of an experimental evaluation.
Decision: Accept (poster)