Individually Fair Diversity Maximization
Authors: Ruien Li
Yanhao Wang
Venue: NeurIPS 2025 poster ()
Keywords: fairness
diversity maximization
Primary area: social_and_economic_aspects_of_machine_learning

Abstract: We consider the problem of diversity maximization from the perspective of individual fairness: given a set $P$ of $n$ points in a metric space, we aim to extract a subset $S$ of size $k$ from $P$ so that (1) the diversity of $S$ is maximized and (2) $S$ is \emph{individually fair} in the sense that every point in $P$ has at least one of its $\frac{n}{k}$-nearest neighbors as its ``representative'' in $S$. We propose $\left(O(1), 3\right)$-bicriteria approximation algorithms for the individually fair variants of the three most common diversity maximization problems, namely, max-min diversification, max-sum diversification, and sum-min diversification. Specifically, the proposed algorithms provide a set of points where every point in the dataset finds a point within a distance at most $3$ times its distance to its $\frac{n}{k}$-nearest neighbor while achieving a diversity value at most $O(1)$ times lower than the optimal solution. Numerical experiments on real-world and synthetic datasets demonstrate that the proposed algorithms generate solutions that are individually fairer than those produced by unconstrained algorithms and incur only modest losses in diversity.

Individually Fair Diversity Maximization
Ruien Li
Yanhao Wang"
School of Data Science and Engineering
School of Data Science and Engineering
East China Normal University Shanghai, China
East China Normal University Shanghai, China
reli@stu. ecnu, edu.
yhwang&dase ecnu. edu. cn
Abstract
We consider the problem of diversity maximization from the perspective of indi- vidual fairness: given set P of points in metric space, aim extract subset S of size k from so that (1) the diversity of maximized and (2) S is individually fair in the sense that every point in P has at least one of its -nearsst neighbors as its "representative" in S. We propose (O(1), 3) 3)-bicriteria approxima- tion algorithms for the individually fair variants of the three most common diversity maximization problems, namely, max-min diversification, max-sum diversification, and sum-min diversification. Specifically, the proposed algorithms provide set of points where every point in the dataset finds point within a distance at most 3 times its distance its -nnarestt neighbor while achieving diversity value at most ((1) times lower than the optimal solution. Numerical experiments on real-world and synthetic datasets demonstrate that the proposed algorithms generate solutions that are individually fairer than those produced by unconstrained algorithms and incur only modest losses in diversity.
Introduction
As machine learning (ML) algorithms are widely used in automated decision-making processes such as banking, hiring, and education, concerns have been raised about their negative social consequences [2], e.g., discriminatory treatment against specific individuals. Recently, there has been extensive literature on algorithmic fairness, aiming to define the notion fairness ML problems and design effective and efficient fairnes--wwan algorithms 31). Such considerations have been taken into account in many data-driven ML tasks, including classification [1], clustering [44), ranking [34 48)
matching (1,, and data summarization g 23
This paper focuses on the diversity maximization problem and addresses its individually fair variants. Diversity mavimization is fundamental combinatorial optimization problem with broad applications in feature selection 477, search [15] 42.. and recommendation
7 Generally, its objective is to extract a subset S of size k from set P of points so that the diversity of S (measured by the point-wise dissimilarity) is maximized. The existing studies on diversity maximization primarily consider three objectives, namely max-min diversification, which aims to maximize the minimum distance between any pair of selected points, max-sun diversification, which aims to maximize the sum of pairwise distances between selected points, and sum mon-min diversification. which aims to maximize the sum of the minimum distances from each selected point to its nearest neighbor among the other selected points. All three problems have been extensively investigated in the literature where they are also, respectively, referred to as remote-edge, remote-clique, and remote panntt--pseudforess.. The unconstrained max-min diversification problem is NP-complete in metric spaces, and greedy algorithm [16] offers a 2-approximation, which has also been shown to be tight [39 For unconstrained max-sum and sum-min diversification problems, is impossible obtain an
6. 9 20 27
Cooresponding Author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

approximation factor better than 2 in polynomial time if we assume that the planted clique conjecture holds 6 [22]. while existing studies have proposed the best possible 2-approximation algorithm for max-sum diversification through greedy selection [19] and the best-known 8-approximation algorithm for sum-min diversification by randomization and solving linear programs (I.Ps) [G] Given that each of these objectives highlights different aspects of diversity, we consider all of them in this paper to obtain a comprehensive understanding of the interplay between diversity and individual fairness in various application scenarios.
Currently, efficient algorithms for diversity maximization under group fairness or partition matroid constraints have been proposed in [2 B
33 45 46). They consider that each point in P denotes an individual associated with a particular demographic attribute, e.g., gender or race. As such, P is divided into different demographic groups, and an algorithm is required to select subset S from P not only to maximize the diversity of S but also to ensure the selection of pre-determined number of points from every group in S for equitable representation. Despite these studies, little attention has been paid to diversity maximization under individual fairness constraints. Inspired by an individual notion of fairness for the facility location problem [2I], the selection of given point set P is fair if' neighbors. Compared with group fairness, individual fairness differs in two crucial aspects. First, it does not require access to group attributes, while group fairness relies on predefined features such as gender, age, or race. Second, the two notions consider different perspectives of fairness. While group fairness emphasizes equitable representation across groups, may overlook disparities among individuals within each group. Individual fairness, by contrast, operates at the point level to ensure that each individual is adequately represented in the selected subset.
every point in P has a center among its ([Pl/k))closee
The need for individual fairness, in particular, is natural and reasonable in many scenarios 9
24 38 40). For instance, consider a fast-food franchise that selects supply outlets within a city. From the perspective of dispersion and diversity, we need to choose outlet locations that are spread out to avoid over-concentration in one region, thereby increasing overall market coverage and potential revenue. However, such dispersion strategies may still leave many individuals far from any chosen outlet, thus excluding them from convenient services. Incorporating individual fairness can address this issue by ensuring that each resident lies within reasonable distance of at least one facility so that no individual is neglected. This balance not only enhances potential revenue but also improves the service experience for all customers, underscoring the need to balance diversity objectives with individual fairness considerations.
13
Our Contributions. With these motivations, we study the problem of a--air k-selection under individual fairness constraints for the three common diversity maximization problems. Here, the parameter a 2 1 can be viewed as fairness tolerance level. Larger a values allow a looser notion of fairness and thus potentially more diverse solutions, while a = corresponds to the strictest form of individual faimess. Moreover, our algorithms are analyzed under the notion of (3, ( bicrrieeria approximation, which means that they may relax the fairness constraints with a factor of y (e.g.. allowing each point to be covered within small multiplicative slack) while still providing provable guarantees on the achieved diversity within a factor of B. Our main results include the following.
Max-Min Diversification: For any a 2 and k E Z4, we give a (3,3)-bicride) -i-biiiita approxi- mation algorithm for max-min diversification under individual fairness constraints if there exists a 8-approximation algorithm for max-min diversification under partition matroid constraints. Using the approximation algorithm of [46] as a subroutine, the approximation factor can be instantiated as (5 + 3) for any >> 0.
For any 2 and k Z,,, we give a (8(4 [ 3), 3)bbccriterii approximation algorithm for max-sum diversification under individual fairness constraints if there exists a 3-approximmttion algorithm for max-sum diversification under partition matroid constraints. Using the 2-approximation local search algorithm in 2 as a subroutine, the approximation factor can be instantiated as (8 + 3, for any E > 0.
Max-Sum Diversification:
Sum-Min Diversification: For any a 2 1 and & < n/3, we give a
approximation algorithm for sum-min diversification under individual fairness constraints if there exists a (3-apprxximation algorithm for sum-min diversification under partition matroid constraints. Using the I.--d 8-approximation algorithm in (6] as a subroutine, the approximation factor can be instantiated as (32 + e, 3) for any 0.

---

To the best of our knowledge, these are the first algorithms with theoretical guarantees for individually fair max-min min, max-sum, and sum-min diversification problems. Finally, we evaluate the empirical performance of our algorithms on real-world and synthetic data sets. The results demonstrate that our algorithms generate solutions that are individually fairer than those produced by unconstrained algorithms while incurring modest diversity losses. In addition, our algorithms also exhibit high time efficiency and scalability.
2 Related Work
(Unconstrained) Diversity Maximization. Diversity maximization has been studied from a graph- theoretic perspective since the 1990s. Ravi et al. [39 proposed a 2-approximation algorithm for max-min diversification and proved that the bound cannot be tighter unless P = NP. Hassin et al. [9] proposed a 2-approximation algorithm for max-sum diversification, and Bhaskara et al. [6] further proved that the approximation factor cannot be improved under the planted clique assumption [22]. Chandra and Halldórsson [9] proposed a Ollog n) -aapproximation algorithm for sum-min diversification. Bhaskara et al. (6] further proposed
8-approximation algorithm for sum-min diversification and proved that the factor cannot be better than 2 under the same planted clique assumption. These algorithms cannot be used for diversity maximization variants with group or individual fairness constraints. Nevertheless, they often serve as building blocks for the design of fair diversity maximization algorithms.
Diversity Maximization under Group Fairness Constraints. Moumoulidou et al. 33 first pro- posed approximation algorithms for the group-fair variant of max-min diversification. Addanki et al. 3 improved the approximation ratios of the algorithms in [33]. Wang et al. [45] proposed streaming algorithms for the group-fair variant of max-min diversification. Wang et al. [46 developed exact algorithm and a (5 + E) -approoximation algorithm for max max-min diversification with bounded-size group fairness constraints. Abbassi et al. [2] proposed 2-approximation local-search algorithms for max-sum diversification under matroid constraints. Bhaskara et al. 66 proposed an 8-approximation algorithm for sum-min diversification under matroid constraints based randomization and linear programming. Mahabadi and Trajanovski (28 proposed two deterministic algorithms for sum-min diversification under group fairness constraints. One is a O(m- log -)-aprpoximaaionn algorithm with an exponential time complexity w.r.t. k. and the other is a Omm² log k) -ppppooxinnttion algorithm that runs polynomial time. Mahabadi and Trajanovski (28) also proposed coreset-based algorithms for max-sum and max-min diversification under group fairness constraints. However, the above algorithms only consider group fairness (or general matroid) constraints and cannot be directly used in the individually fair variants of diversity maximization.
Individual Fairness in Clustering Problems. Clustering has been studied extensively from fairness perspective over the past few years. Most previous results consider clustering problems under the notion of group fairness [1 [4] 23 Jung al. [21] first proposed the notion of individual
fairness we use in this paper for facility location problems. Following this seminal work, individually fair clustering problems have attracted some attention in recent years. Mahabadi and Vakilian [29 studied center-based clustering problems, such as k-median, k-means, and k-center, with individual fairness constraints. Negahbani and Chakrabarty [35] explored individually fair k-clustering with general l, fo-orrm objectives using a linear programming approach. Vakilian and Yalçiner [44) studied the problem of f--rir k-clustering with (p-norm objectives, achieving improved approximation factors in both fairness and cost. Han et al. [17] considered individually fair k-center with outliers and proposed a 4-approximation algorithm. Bateni et al. [5] designed a fast local-search algorithm for individually fair k-means clustering with improved time complexity. These approaches provide inspiration for the algorithms presented this paper. However, they cannot be applied directly to diversity maximization, as they are originally designed for clustering problems.
3 Problem Definition
Let (P, d) denote a metric space, where a set of n points and d P P Rzo a distance function that measures the dissimilarity between any pair of points in P and satisfies the axioms of (i) identity of indiscernibles, (ii) symmetry, and (iii) triangle inequality. We use C P to denote a subset of points. The number of points to select, unless otherwise specified, is denoted by k E E+.
3

---

Then, we define the objective functions of the max-min, max-sum, and sum-min diversification as follows. They are all distance-basec based objectives; that is, they are formulated in terms of the pairwise distances between the chosen points. Let d(u, v) be the distance between and v, and for a set of points T, let d(u, T) min d(u, v). The diversity functions for the three objectives are as follows:
1. Max-Min Diversification: div (S, P) = minges d(u, SMu3))
2. Max-Sum Diversification: div ( (S, P) - Eves Evesy(y) d(u,));
3. Sum-Min Diversification: divam (S, Eves d(u, Muf)).
Max-min diversification aims to maximize the minimum distance between any pair of distinct points in the selected set S. Intuitively, it encourages the selected points to be as far apart as possible, ensuring separation among all points. Max-sum diversification aims to maximize the sum of all pairwise distances among the points in the set Thus, favors set in which the points are collectively dispersed across the space. Sum-min diversification aims to maximize the sum of the distances from all points u E S to their nearest neighbor within \\ {u]. strikes a balance between local and global diversity, promoting selections where each point is relatively well-separated from at least one close neighbor, without maximizing all pairwise distances.
Next, we introduce some notation to formally define the notion of individual fairness we consider in this paper. For every point v E P. we use Bie, r) := {u E P d(v, u) S. r) denote the subset of all points in P' that are at distance at most from v and call it the ball of radius centered at e.
Definition 1 (Fair Radius). Let l E [n]] be a fairness parameter: For every point v E P, we define the fair radius ri (1) as the minimum distance such that [B(rr)) 2 7. When I k, we drop the subscript for simplicity and use r(-) to denote (+)-).
Then, we formally define the notion of a-fair k-selection 44), a variant of the individual fairness notion from 21 29
Definition 2 (a-Fair k-Selection). set of ls points S S P a-fair if for every point E P. d(x, S (r).
According to [21], there always exists a feasible solution when a 2 2. Ideally, we would like to find solution with
1, which would fully satisfy the original definition of individual fairness However, since deciding whether a given set of points admits a fair selection with a = 1 is NP-hard (1],, it is unlikely that such solutions can be found in polynomial time unless P NP. Consequently, we aim to provide a bicriteria approximation guarantee instead.
21 22
Definition 3 (Bicriteria Approximation). An algorithm is a (3, 7.iiriiiii approximation for a-fair k-selection w.r.t a given diversity function if for any set of points P the solution SOL returned by the algorithm on P satisfies the following properties:
1. div(O P) < B Biviv P), where OPT denotes the optimal set of k points for a a-fair k-selection of P w.r.t the given diversity function. In particular, div(OPT, 0 an a-fair k-selection does not exist P.
2. SOL is a (y aa)ffiir k-selection of P.
Hardness of Approximation. Ravi et al. (39] showed that, unless P NP, there does not exist any polynomial- 3-approximation algorithm for the unconstrained max-min diversification problem when 3 < 2. Bhaskara et al. [6] further proved that, under the planted clique conjecture, there exists no polynomial-time 3-approximation algorithm for the unconstrained max-sum and sum-min diversification problems when 3 < 2. Since the unconstrained setting can be viewed as the special case of our individually fair setting with a = oo, the hardness results in the unconstrained case naturally generalize to our problems, as stated below.
Theorem 1. There exists polynomial-time --approximation algorithm for individually fair max- min diversifcation with 3 < 2, unless P = NN.
Theorem 2. There exists no polynomial-time 3-aaproximattin algorithm for individually fair max- sum and sum-min diversification with 3 <, 2 under the planted clique conjecture.

---

Algorithm 1: IFRGENERATE
Input:
Fairness parameter
Output: A set of individual fairness regions for given parameters (r Initialize the set of covered points Z 0 and the set of centers of selected balls C 0
while Z * P do
c arg min r(x)
C CUfcc
+ Z f ( s) 2a r(()
end while
return ((ccaar(C)::ces
connections between individual fairness In previous studies on individually fair clustering 29
44
and partition matroid constraints have been established. We now introduce the concept of matroid constraints so that our subsequent individually fair algorithms can be framed as solutions rooted in them. Note that the group fairness constraint has also been shown to be a type of matroid constraint.
Definition (Matroid Constraint). matroid M defined as a family of subsets of the ground set of points E(M) P. called independent sets. The set of independent sets S of matroid M is denoted by I(M). For given matroid M, the associated matroid constraint
E I[M). As is standard, M is uniform matroid of rank (fM {X C E(M) : |X| S r.. A partition matroid is the direct sum of uniform matroids. Note that uniform matroid constraints are equivalent to cardinality constraints, ie.. [S| S k. This definition follows 43
To satisfy individual fairness constraints, we introduce a special structure called individual fairness regions, which partitions the points based their distances in the metric space. This notion is useful in our algorithms for connecting individual fairness to matroid constraints.
Definition 5 (Individual Fairness Region). set of balls = [B(c1, aer((c))....... B(cm & o-r((m))) where S k; is called a set of individual fairness regions it satisfies the following properties:
1. For every x E P. d(x, Cmm)) S 2a r(x);
2. For any pair of centers G2 Cj. d(cs; 0ÿ) > 2a max(r(c),r((s)) in other words, individual fairness regions are disjoint from each other.
Our Algorithms
In this section, we reduce our individually fair diversity maximization problem to data selection under partition matroid constraints. We first present an algorithm, IFRGENERATE, that, given a set of points P and a fairness parameter a, returns a set of individual fairness regions.
Overview of Algorithm 1 IFRGENERATE is designed to address the problem of maximizing diversity under individual Tairness constraints by reducing it to the problem under partition matroid constraints. Similar algorithms have been used for individually fair clustering, and they crucial for satisfying individual fairness constraints in clustering problems [2]444 44]. The algorithm takes as input fairness parameter a, the size of the input data set n, and the desired size of the output set k. The procedure begins by initializing two empty sets: a set of covered points Z + 0 and a set of long the set of uncovered points
selected ball centers C <- 0. It then enters loop that continues P Z is non-empty. At each iteration, the algorithm selects a center c that has the minimal fair radius in the uncovered points, adds including all points E P P\ Z whose distance d(r, e) is at most 2a r(x). This process repeats until all points are covered. The output of the algorithm
the set of centers C, and updates the set of covered points Z by
set of balls { B(c, ar(c)) e E C). where each ball should consist of a selected center and its radius (r((c.. This set of balls can be treated as different groups, connecting our problem with that under the partition matroid constraints.
We now prove that IFRGENERATE generates individual fairness regions as defined in Definition Lemma Let be positive integer and a be a parameter that indicates the desired fairness guarantee. Algorithm 1 returns set of at most k individual fairness regions in O(nk) time.
5

---

Algorithm 2: OMSGENERATE
Input:
Set of points P, desired number of selected points k fairness parameter
Output:
Individual faimess regions and k; in the original metric space
Compute set of individual fairness regions B = (B1, ... Bm ) on (P, k. a:) using Algorithm |
Let Po = {volv E (BB U..-UU ]m]} be the points not in individual fairness regions
k; k- m for all i [m]] D (denote that we pick at most k m + 1 centers from each
individual fairness fairnes ball)
ku k [denote that we pick most centers from Pol return {PPo ko), (B1, k1).... ... (Bm, (Bm.km)) km))
See the proof in Appendix B.I of individual fairness regions is that it reduces the problem of finding an o-fair selection selection problem with lower bound requirements, i.e., at least one point must be selected from each individual fairness region. Lemma [ indicates that a set of points S feasible w.r.t. set of individual fairness regions B, if for every ball B E B, |S n BI >> O.
Similar to individually fair clustering (29 44 the benefit of a set data
r(c:)) (...aar((e))))) .... B(cm. a r((m))) be a set of individual fairness regions obtained from Algorithm 7 for a set of points P with parameters k and a. Then, any set of points S that is feasible w.r.t. B is (3ar)fairr
Lemma 2.
Let B [B(c,, a
See the proof in Appendix B.2, Based on the lemmas above, we now introduce our algorithm for maximizing diversity under individual fairness constraints. We first construct individual fairness regions on the original data / using A
OMSGENERATE is designed to address the problem of selecting diverse subset of points while satisfying the fairness constraints in the given dataset P. specifically by generating a set of individual fairness regions in P. The algorithm takes input a set of points P, a desired number of selected points k, a fairness parameter a and the original metric space. It begins by computing a set of individual fairness regions B [BI.... Bm } using Algorithm I (IFRGENERATE) on the imput (P, k a). Next, it identifies the set of points Po that are not covered by these fairness regions, i.e., points outside the union of all fairness regions in B. For each individual fairness region B;, the algorithm sets the maximum number of points that can be selected from B, at k; = m + In addition, it sets ky = k. which is the maximum number of centers that can be selected from the uncovered points Po- Note that ka, ki...., kim do not denote the number of points that should be selected but the maximum number that can be selected in a region. In practical implementations, the number of points to be selected may differ from ko, ki,.... km as they are only the upper bounds on the number of points to select. Our ultimate goal is always to select k points the final result. Finally, the algorithm returns a set of individual fairness regions (Po, ko), (B1, kt)..... (Bm, }. representing the individual fairness regions in P and the maximum number of points that can be selected from each region. Since the computation can be mainly attributed to Algorithm| [ the time complexity of Algorithm 2 is (mk) as well.
Overview of Algorithm 2
Now, we demonstrate that with a 3-approximation algorithm for different diversity maximization problems under partition matroid constraints. a bicriteria approximation for a-fair k-selection exists. We first give the approximation for max- max-min diversification under individual faireess constraints.
Theorem 3. Suppose that there exists a 3-approximation algorithum for max-min diversification under partition matroid constraints. Then, there exists (3, -iicriiterr approximation for a-fair k-selection in max-min diversification.
Proof Sketch. We show that the solution from a 8-approximation algorithm (MAXMINALG) for max-min diversification under partition matroid constraints is a (3, 3) -bbcritteria approximation for a-fair k-selection metric space P. The solution SOLG from MAXMINALG satisties the partition matroid constraints, ensuring at least one point per fairness region B, By Lemma 2 this implies that SOLG is ffir- We show that the diversity of the optimal solution OPT on P is equal to that of OPT (7 on constructed instance P'. By mapping the solutions between P and P', we show divmm (OPT P) divmm (OPT', P').
For the f--riir optimal solution OPT, on P. we can construct a feasible solution OPT on P' with equal diversity while satisfying the partition matroid constraints. Since OPT is opti-

---

mal on P', divmm divmm (OPT
C. P') = div mm (OPT,, P). Given that MAXMI- NÁLG is B-approximate, dm (OPT P) 3 divmn(SOLc. P). thus div P)
P!) > div mm (OPT
B (SOL.,, P). Therefore, SOL- is a (3, 3)-bicriterria approximation.
See the full proof in Appendix B.4
After proving the existence of bicriteria approximation algorithm for a-fair k-selection with max-min objective, we then prove that the algorithm for the max-sum objective also exists.
Theorem 4. Suppose that there exists a 8-approximation algorithm for max-sum diversification under partition matroid constraints. Then, there exists a (3(4 + +),3) bicciieriia approximation for a-fair k-selection in max-sum diversification.
Proof Sketch. We show that the solution from a B-approximation algorithm (MAXSUMALG) for max-sum diversification under partition matroid constraints a (3(4+ 3)) -biriiteria approximation for a-fair k-selection on metric space P. We establish that div (OPTc, P) 2 + div (OPT', P'). When niv (OPTG, P) divms(OPT' o P'), OPT may include multiple copies of points in P. In the extreme case, points in P' map to points in P, and analyze basic cases (e.g., four points in P' from two in P) show div (OPT' P') < (4++)-diva, (ORI, P), where ORI are distinct points in P. Since (OPT P) 2 div (ORI, P), we get mi. (OPTa. P) 2 - div P').
For the a-fair optimal solution OPT, on P. we construct OPT on P with equal diversity while satisfying the partition matroid constraints. Since OPT, is optimal on P divms (OPT P') Z divms (OPT c: P') = div (OPT,, In combination with the 5-approximation of MAXSUMALG, div ms (OPT,, P) S (4 + E) div (OPT.. P) s 3(4 + E) mi 100G,.)) P). Therefore, SOLG is (B(4 + e), 3) biccritta approximation.
See the full proof in Appendix B.5
We then consider the same circumstance for sum-min diversification.
Theorem 5. Suppose that there exists a 3-approximation algorithm for sum-min diversification under partition matroid constraints with 1 < k < n/3. Then, there exists (3(4 s), 3),3)--icriteria approximation for o-fair k-selection in sum-min diversification.
Proof Sketch. We show that the solution from 3-approximation algorithm (SUMMINAL.G) for k- selection under partition matroid constraints for sum-min diversification is a (3(4 + E), 3)-bicrit approximation for a-fair k-selection on metrie space p. We establish that div (OPT " P) > IFe div (OPTo, P'). When div P) < div.. sm ,OPT', P'), OPT includes multiple copies of the points in P. With
k distinct points in P corresponding contribute 2(k - =)εō to dOV P'). Defining D = div.. (OPT a P') 2(k 2)cō. we show D < div.. (OPTs P), where OPT: is the optimal z-point solution in P. By Lemma (see Appendix B.6). div (PP P) < 4- div (OPT P) for 1 < k < n/3. Since 2(k 2jEd s
OPT pairs of copies
div.m OPT,, P). get dOV P') (4+ +)+ ddiv.. P).
For the a-fair optimal solution OPT, on P, we construct OPT on p' with equal diversity satisfying partition matroid constraints. Since OPT is optimal on P', div, (OPT', P*) 2 div.m (OPT) P') divam OPT, P). Combining with the 3-approximation of SUMMINALG, divam (OPT,, T P) (4
E) div sm (PPT,, P) < 3(4 e)) div,m (SOLe, P). Therefore. SOLG is (8(4 + E), 3))rrbbirii approximation.
See the full proof in Appendix
B.6
According to Theorems 3 5 we have the following theorems with specific approximation factors.
Note that the computation of differs between these theorems; detailed explanations are provided in Appendix C
Theorem 6. For any 2 1, there exists O + m log 2) time algorithm that computes (5 + e, e, bicriteriia approximate solution to the a--aiir k- k-selection of max-min diversification under individual fairness constraints.
7

---

The proof follows from Theorem 3 and the (5 + e) apprrxxmaatno algorithm from [46 for max-min diversification under partition matroid constraints. We note that the time complexity of this algorithm is not linear w.r.t. k. More detailed discussions are provided in Appendix [
Theorem 7. For any 1, there exists polynomial time algorithm that computes (8 + E. bicriteria approximate solution to the a-fair k-selection of max-sum diversification under individual faimess constraints.
The proof follows from Theorem 4 and the 2-approximation algorithm in 2 for max-sum diversifica- tion under partition matroid constraints.
Theorem 8. For any a 2 1, there exists nearty linear-time time algorithm that computes a (32 + E, 3) bicriteria approximate solution the a-fair k-selection of sum-min diversification under individual fairness constraints.
The proof follows from Theorem and the 8-approximation algorithm in 6 for sum-min diversifica- tion under partition matroid constraints.
5 Experiments
In this section, we empirically compare our algorithms with unconstrained diversity maximization algorithms. The experiments focus presenting the trade-off between fairness and diversity loss of our algorithms.
Implementation. All experiments were carried out on a server with an Intel(R) Xeon(R) Gold 6134 CPU @e3.20HH (2 processors) and 1 128GB RAM running Windows Server 2019 Datacenter. The algorithms were implemented in Python 3. Our code and data are publicly available at https //github. w/g.tthub.cmm/Hooooooo com//Honokkkoouuaaa//Eoy
Data Sets. the experiments, we used three public real-world data sets and one synthetic data set. The basic information for each data set is shown in Table For MovieLens, the user vectors are obtained through matrix factorization using LIBMF [1]. We randomly sampled 1,000 points from each data set for evaluation.
Table 1: Statistics of data sets in the experiments, where n is the number of data points and dim is the dimensionality.
Dataset
Description
dim
CelebA (26
Features for celebrity images extracted by VGG16
202,599
25,088
GloVe (37
Global vectors for word representation
400,000
100
MovieLens [18]
User vectors obtained from the rating matrix
162,541
50
Gaussian
Gaussian blobs by make_ble blobs in scikit-learn
36
1,000,000
20
Experimental Setup. For max-min diversification under individual fairness constraints, we im- plemented FMMD-S [46]. a (5 + -paappoxxitttionn algorithm for max-min diversification under partition matroid constraints in Ommn + m log ! time, and fixed æ = 0.05 for FMMD-S. We com- pared our algorithm with GMM (16), which provides a 2-approximation for unconstrained max-min diversification. For max-sum diversification under individual fairness constraints, we implemented the local search algorithm in 2). which is 2-approximation algorithm for max-sum diversification under general matroid constraints in O log(k)) time, and set ø 0.05 in the algorithm. We compared our algorithm with the greedy algorithm in [19) which guarantees a 2-approximation for unconstrained max-sum diversification. For sum-min diversification under individual fairness constraints, we implemented the foreset-based algorithm in (28), which provides an O(m² log k)- approximation for sum-min diversification under group faimess constraints in polynomial time. To obtain an unconstrained solution for sum-min diversification, we placed all points in an individual fairness region and ran our algorithm accordingly. We fixed a = 1 in all experiments so that each algorithm makes the best effort to ensure individual fairness. We implemented all algorithms in Python 3 and used the Gurobi optimizer to solve ILPs in FMMD-S. To compare with unconstrained optimal solutions for quantifying exact utility losses, we also ran the Gurobi optimizer to solve the ILPs for max-min, max-sum, and sum-min diversification within 30-minute time limit.
8

---

11
Max-Min
11
Mox-Sum
11
SamsMin
1.0
Rato
0.0
0.0
0.0
10
10
15
25
10
2.0
1.8
18
1.6
16
3.4
114
1.2
12
12
1.0
10
1.8
0.8
5
10
15
20
40
65
04
10 15
0.8
10
35
50
Figure 1: Overall experimental results. The first row illustrates the ratios of the diversity values of the solutions returned by our algorithms over the diversity values of the best solutions returned by unconstrained algorithms when 2,5, 10, .0.....55 50 and a = the second row presents the Omax values of the solutions returned by our algorithms.
Evaluation Measures. In terms of individual fairesss, we define Qmax max.e d(x, SOL)/r(x)
as the performance metric. Specifically, Omax indicates how close solution is to satisfying the individual fairness constraint on P: The smaller Ommax the fairer the solution SOL. If O'ax S 1, the solution SOL strictly satisfies the individual fairness constraint. In terms of utility, we compute the ratio of the diversity value of fair solution to that of an unconstrained solution returned by an approximation or an exact ILP-based algorithm, using this ratio as the performance metric. The larger the ratio, the higher the utility of the solution. When using approximation algorithms to obtain unconstrained solutions, we ran them 10 times and selected the solution with the largest diversity value. We also ran proposed algorithms ten times and used the average of both measures for evaluation.
Experimental Results. In Figure 1 we present the experimental results for three diversity objectives across four data sets. We observe that our algorithms consistently provide approximate solutions with diversity losses of no more than 30% compared to unconstrained (approximate) solutions, while always guarantecing that the value Qmax below 2. In Table we also present the ratios of the diversity values of our solutions to the optimal diversity values computed from the ILPs solved by Gurobi. As shown, our algorithms limit utility losses relative to unconstrained (optimal) solutions to most 35%, further validating their effectiveness in ensuring diversity while satisfying individual fairness constraints. These results demonstrate that our algorithms strike an effective balance between individual fairness and diversity.
Table Ratios of the diversity values of the solutions of our proposed algorithms over the diversity values of the optimal unconstrained solutions by ILPs when k 10, 20 and 1.
Max-Min
Max-Sum
Sum-Min
Dataset
k 5
k 10
20
k
5
k
10
A: 20
k:
k 10
k 20
CelebA
0.827
0.807
0.794
0.923
0.967
0.985
0.703
0.769
0.842
GloVe
0.780
0.793
0.824
0.947
0.980
0.991
0.754
0.835
0.910
MovieLens 0.701
0.724
0.764
0.925
0,961
0.977
0.676
0.757
0,830
Gaussian 0.819
0.845
0.819
0.968
0.988
0.996
0.831
0.893
0.955
Figure shows the running times of our algorithms on each data set. In terms of time efficiency, taking CelebA as an example, the process of computing an individually fair solution (including Algorithms D 2 and the diversification algorithms with matroid constraints) takes no more than 4 seconds when & < 50 for max-min and sum-min diversification. For max-sum diversification, because & is very small, the local search requires many iterations to meet the stop condition; thus,
takes about 300 seconds when & = 50.

---

300
240
1000
0.4
120
0.2
50 10
Figure 2: Running time (in seconds) of our algorithms when k = 2, 5, 10...... 50 and a
We observe that when & 50, the synthetic Gaussian data set exhibits anomalous results in the ratios, the mmx values, and the rumning time for max-sum and sum-min diversification. This phenomenon can be attributed the data generation process, since the Gaussian data is constructed by sampling points around 50 Gaussian centers. As result, when k 50, the data set naturally forms exactly 50 individual fairness regions, each containing 20 points. Consequently, every data point falls into one of these regions, and selecting one point from each region is sufficient to achieve high diversity while guarantecing individual fairness. This leads to Q < when h = 50; that is, the proposed algorithms provide solutions that strictly satisfy the individual fairness constraints. Moreover, for max-sum diversification, the local search procedure requires only a few iterations before meeting the stop condition because the initial solution already contains one point from each region. In contrast, for sum-min diversification, our proposed algorithm uses GMM to fit within each of the 50 fairess regions and determine potential candidates. Consequently, performing 50 independent GMM instances significantly increases the runtime when 50.
6 Conclusion
In this paper. we study the diversity maximization problem under individual fairness constraints, namely a-fair k-selection. By generating individual fairness regions to partition data points and utilizing existing approximation algorithms for diversity maximization under matroid constraints, we propose a (5 + E, 3---33)---ttt bicriteria approximation algorithm for max-min diversification, (8 + e, 3) bicriteria approximation algorithm for max-sum diversification, and (32 + c, 3)-bicriteriia approxima- tion algorithm for sum-min diversification for any a 2 1 in any metric space. Experimental results demonstrate that our proposed algorithms efficiently provide individually fair, highly diverse subsets on real-world and synthetic datasets.
There are still some open problems for future work. Given that the approximation factors of our algorithms are determined by those for diversity maximization under matroid constraints, possible direction improve the approximation ratio for individually fair diversity maximization by utilizing better
diversity maximization algorithms. In addition, we acknowledge that we have not proved whether individually fair diversity maximization problems are strictly harder to approximate than their unconstrained counterparts. Establishing such hardness results remains open and would shed light on further improvements in approximation factors. Another promising avenue for exploration is to extend the problems and proposed algorithms to streaming, distributed, and deletion-robie robust settings.
Acknowledgments and Disclosure of Funding
This work supported by the National Natural Science Foundation of China (Grant No. 62202169).
References
[1] 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 514, 2021.
10

---

[2] Zeinab Abbassi, Vahab S Mirrokni. and Mayur Thakur. Diversity maximization under matroid constraints. In Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 52-40, 2013.
[3] Raghavendra Addanki, Andrew McGregor, Alexandra Meliou, and Zafeiria Moumoulidou. Improved approximation and scalability for fair max-min diversification. In 25th International Conference Database Theory, pages 7:1-7:21, 2022.
[4] Azin Ashkan, Branislav Kveton, Shlomo Berkovsky, and Zheng Wen. Optimal greedy diversity for recommendation. In Proceedings of the Twenty-Foures International Joint Conference on Artificial Intelligence, pages 1742-1748, 2015.
[5] MosammadHosseein Bateni, Vincent Cohen-Addad, Alessandro Epasto, and Silvio Lattanzi. A scalable algorithm for individually fair k-means clustering. In Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, pages 3151-3159, 2024.
[6] Aditya Bhaskara, Mehrdad Ghadiri, Vahab S. Mirrokni, and Ola Svensson. Linear relaxations for finding diverse elements in metric spaces. Advances in Neural Information Processing Systems, 29:4098-4106, 2016.
[7] Pablo Castells, Neil Hurley, and Saúl Vargas. Novelty and diversity in recommender systems. In Francesco Ricci, Lior Rokach, and Bracha Shapira, editors, Recommender Systems Handbook, pages 603-646. Springer, New York, NY, USA, 2022.
[8] Elisa Celis, Vijay Keswani, Damian Straszak, Amit Deshpande, Tarun Kathuria, and Nisheeth Vishnoi. Fair and diverse DPP-based data summarization. In Proceedings of the 35th Interna- tional Conference on Machine Learning, pages 716-725, 2018.
[9] Barun Chandra and Magnús M Halldórsson. Approximation algorithms for dispersion problems.
J. Algorithms, 38(2):338-465, 2001.
[10] Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii. Fair clustering through fairlets. Advances in Neural Information Processing Systems, 30:5029-5033 2017.
[11] Wei-Sheng Chin, Be Yuan, Meng- Yuan Yang, Yong Zhuang, Yu-Chin Juan, and Chih-Jen Lin. LIBMP: a library for parallel matrix factorization in shared-memory systems. J. Mach. Learn. Res., 17(1):2971-2977 2016.
[12] Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, pages 214-226, 2012.
[13] Erhan Erkut. The discrete p-dispersion problem. Eur. J. Oper. Res., 46(1):48 60, 1990.
[14] Mehrdad Ghadiri, Samira Samadi, and Santosh Vempala. Socially fair k-means clustering. In Proceedings of the 2021 ACM Conference Fairness, Accountability, and Transparency, pages 438 448, 2021.
[15] Sreenivas Gollapudi and Aneesh Sharma. An axiomatic approach for result diversification. In Proceedings of the 18th International Conference World Wide Web, pages 381-390, 2009.
[16] Teofilo F Gonzalez. Clustering to minimize the maximum intercluster distance. Theor, Comput. Sci., 38:293-306, 1985.
[17] Lu Han, Dachuan Xu, Yicheng Xu, and Ping Yang. Approximation algorithms for the individu- ally fair k-center with outliers. J. Glob. Optim., 87(2):603-61 618, 2023.
[18] F. Maxwell Harper and Joseph A. Konstan. The movielens datasets: History and context. ACM Trans. Interact. Intell. Syst., 5(4):19:1-19:19) 2016.
[19] Refael Hassin, Shlomi Rubinstein, and Arie Tamir. Approximation algorithms for maximum dispersion. Oper. Res. Lett., 1333:1333-137, 1997.
[20] Piotr Indyk, Sepideh Mahabadi, Mohammad Mahdian, and Vahab S Mirrokni. Composable core-sets for diversity and coverage maximization. Proceedings of the 33rd ACM SIGMOD- SIGACT-SIGART Symposium on Principles of Database Systems, pages 100-108, 2014.
[21] Christopher Jung, Sampath Kannan, and Neil Lutz. Service in your neighborhood: Fairness in center location. In /st Symposium on Foundations of Responsible Computing, pages 5:1-5:15, 2020.
11

---

[22] Richard M. Karp. The probabilistic analysis of some combinatorial search algorithms. Technical Report UCB/ERL M581, University of California, Berkeley, Apr 1976. http:///://ww eecs. berkeley bercs.eerkeeeeyeedd//iuuee wwwpeed./uuuuueeeeee wttpPatt//.eectattaaaaaerieieeee
html
[23]] Matthäus Kleindessner. Pranjal Awasthi, and Jamie Morgenstern. Fair k-center clustering for data summarization. In Proceedings of the 36th International Conference on Machine Learning.
pages 1448-3457) 2019.
[24] Michael Kuby. Programming models for facility dispersion: The p-dispersion and maxisum dispersion problems. Geogr. Anal., 19(4):315-32, 1987.
(25) Yash Kurkure, Miles Shamo, Joseph Wiseman, Sainyam Galhotra, and Stavros Sintos. Faster algorithms for fair max-min diversification in Rd Proc. ACM Manag, Data, 17:31137 2024.
[26] Ziwei Liu, Ping Luo, Xiaogang Wang. and Xiaoou Tang. Deep learning face attributes in the wild. In 2015 IEEE International Conference on Computer Vision, pages 3730-3738, 2015,
[27] Sepideh Mahabadi and Shyam Narayanan. Improved diversity maximization algorithms for matching and pseudoforest. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 25:1-25:25 2023.
[28] Sepideh Mahabadi and Stojan Trajanovski. Core-sets for fair and diverse data summarization. Advances in Neural Information Processing Systems, 36.78987-79011, 2023.
[29] Sepideh Mahabadi and Ali Vakilian. Individual faimess for k-clustering, In Proceedings of the 37th International Conference on Machine Learning, pages 6586-6596, 2020.
[30] Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. A survey on bias and fairness in machine learning. ACM Comput. Surv. 34(6):115:1-))) 15:11115333 2022.
[31] Shira Mitchell, Eric Potash, Solon Barocas, Alexander Amour, and Kristian Lum. Algorithmic fairness: Choices, assumptions, and definitions. Annu. Rev. Stat. Appl., 8:141-163, 2021.
[32] Brent Daniel Mittelstadt, Patrick Allo, Mariarosaria Taddeo, Sandra Wachter, and Luciano Floridi. The ethics of algorithmss Mapping the debate. Big Data Soc., 3(2):1-21, 2016.
[33] Zafeiria Moumoulidou, Andrew McGregor, and Alexandra Meliou. Diverse data selection under fairness constraints. In 24th International Conference on Database Theory, pages 13:1-13:25,
2021.
[34] Harikrishna Narasimhan, Andrew Cotter, Maya Gupta, and Serena Wang. Pairwise faimness for ranking and regression. Proceedings of the AAAI Conference on Artificial Intelligence, 34(04): 5248-5255, 2020.
[35] Maryam Negahbani and Deeparnab Chakrabarty. Better algorithms for individually fair k- clustering. Advances in Neural Information Processing Systems, 34:13340-13351, 2021.
[36] Fabian Pedregosa, Gaäl Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit- learn: Machine learning in Python. J. Mach. Learn. Res., 12:2825-2830, 2011.
[37] Jeffrey Pennington, Richard Socher, and Christopher D. Manning. GloVe: Global vectors for word representation. In Proceedings of the 2014 Conference Empirical Methods in Natural Language Processing, pages 1543, 2014.
[38] Nikolaos Ploskas, Kostas Stergiou, and Dimosthenis Tsouros. The p-dispersion problem with distance constraints. In 29th International Conference Principles and Practice of Constraint Programming, pages 30:1-30: 18, 2023.
[39] Sekharipuram Ravi, Daniel Rosenkrantz, and Giri Kumar Tayi. Heuristic and special case algorithms for dispersion problems. Oper: Res., 42(2):299-3101 1994.
[40] SS Ravi, Daniel J Rosenkrantz, and Giri K Tayi. Approximation algorithms for facility dispersion. Handbook of Approximation Algorithms and Metaheuristics, pages 347-364. Chapman and Hall/CRC, 2018
[41] Govind S Sankar, Anand Louis, Meghana Nasre, and Prajakta Nimbhorkar. Matchings with group fairness constraints: Online and offline algorithms. In Proceedings of the Thirtieth International Joint Conference Artificial Intelligence, pages 377-383, 2021.
12

---

[42] Rodrygo L. T. Santos, Craig Macdonald, and ladh Ounis. Exploiting query reformulations for web search result diversification. In Proceedings of the 19th International Conference on World Wide Web, pages 881-890, 2010.
[43] Alexander Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin, Heidelberg. 2003.
[44] 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, pages 8758-8779, 2022.
[45] Yanhao Wang, Francesco Fabbri, and Michael Mathioudakis. Streaming algorithms for diversity maximization with fairness constraints. 2022 IEEE 38th International Conference on Data Engineering, pages 41-53, 2022.
[46] Yanhao Wang, Michael Mathioudakis, Jia Li, and Francesco Fabbri. Max-min diversification with fairness constraints: Exact and approximation algorithms. In Proceedings of the 2023 SIAM International Conference on Data Mining, pages 91-99, 2023.
[47] Sepehr Abbasi Zadeh, Mehrdad Ghadiri, Vahab S. Mirrokni, and Morteza Zadimoghaddamm Scalable feature selection via distributed diversity maximization. Proceedings of the AAAI Conference on Artificial Intelligence, 31(1):2876-288) 2017.
[48] Meike Zehlike, Francesco Bonchi, Carlos Castillo, Sara Hajian, Mohamed Megahed, and Ricardo Baeza-Yalee FA*IR: A fair top-k ranking algorithm. In Proceedings of the ACM on Conference on Information and Knowledge Management, pages 1569-1578, 2017.
13

---

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]
Justification:
See the Abstract and Introduction sections.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The limitations are discussed in the Conclusion section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
14

---

Justification:
See the Lemmas and Theorems as well as their proofs in the paper.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We have described the experimental setup in Section
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make clear how to reproduce that algorithm.
(b) If the contribution primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is a new model (e.g., large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
15

---

reproducible, they Answer: [Yes]
Justification:
We have released our code and data a GitHub repository.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https for more details.
/ //nips http::ccpplllliggiiieeee httpg/dddds//oeuubbmmmmmm
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
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: [Yes]
Justification: See details in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
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: [No]
Justification: The experimental results are stable, since the experiments are run across four datasets various parameter settings. We also ran each algorithm that involves approximation and randomization ten times and reported the best (for baselines) or the average (for our proposed algorithms) of each evaluation metric.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by emror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
16

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors Is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative emror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
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?
Question:
Answer: [Yes]
Justification: See details in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: http:::///nuriige http//eurrricccoeo https///........iiicsciiaaaaaaa.
Answer: [Yes]
Justification: Our work does not involve crowdsourcing, contract work. Our work does not involve interactions between researchers and human participants. The datasets being used are open-source or generated by scikit-learn, and we have correctly made citations. We do not identify any deviation from the Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- cration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: In this work, aim to maximize commonly used diversity objective functions while ensuring a certain level of individual fairness. Our algorithm does not involve human intervention in data distribution classification. Our work contributes to raising awareness of fairness and diversity in ML-based Decision-making processes. Generally, we do not foresee any immediate and direct harmful impacts from this work.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
17

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The datasets being used in our paper are open-source or generated by scikit- learn. Therefore, our work does not pose such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
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: [Yes]
Justification: We list the licenses for the assets we use in our work. These assets have been correctly and properly cited in our paper.
Code: Our implementation of the algorithm for sum-min diversification under partition
matroid constraints is partly based the code from 29). which has an MIT license.
Datasets: CelebA is available for non-commereial research purposes, as claimed by the dataset creators on their official website. Movielens can be used for any research pur- poses under their customized Usage License. GloVe available under the Public Domain Dedication and License, claimed by the creators.
Guidelines:
18

---

The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
We have released our code in well-documentedd format.
Guidelines:
The answer NA means that the paper does release assets.
Researchers should communicate the details the dataset/code/mooel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
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 details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
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 equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing research with human subjects.
19

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The algorithm design and proof in this paper do not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does involve LLMs as any important, original, or non non-standard components.
Please refer to our LLM policy for what should or should not be described.
20

---

A
Algorithm 3 (PSGENERATE) (Used for Proof Only)
Consider an instance of a-fair k-selection on a point set P. Let be the set of individual fairness Then, given instance of a-fair k-selection, Algorithm builds an instance k-selection under partition matroid constraints.
regions of P with parameters k and constructed using Algorithm 2
Overview of Algorithm 3 Existing studies on individually fair clustering 44 have implemented similar instance to generate an individually fair solution for clustering problems. Our implementation of Algorithm 3 is little different, since the instance generated is not directly involved in our solution generation process. However, serves a critical role in our theoretical analysis. Unlike prior work, where the constructed instance is typically used the final clustering solution, our approach leverages the instance primarily to facilitate the proof of our theorem guarantees, ensuring that the diversity properties hold under the individual fairness constraints. PSGENERATE takes as input a point set P. the desired number of selected points k, faimess parameter a, and an accuracy parameter fairness regions = .i..... , Bm using Algorithm 2 on (P, k. a:.. Next, it creates copies of the original point set P and each individual fairness region B, denoted as Po and B, respectively, and constructs an extended set P' by including Po and B, Note that P' has two distinet copies of the points that belong to an individual fairness ball of B. A modified distance function d' is then defined, where d' d'(u, u) = 0 for all u P', d' (V,, Uyy - d(v, u) for distinct c, u E P with v A u, and d' (Ua, vyy) = eg for Un, Uy E P", where ô f- min d(2 v)- The algorithm finally returns the tuple (P', ((Po, To)), BB1, Ri),...., (Bm, Ten. )}, d'), providing an instance corresponding the
direct component in producing
1/2. It begins by computing set of individual
given o-fair k-selection problem for the proof purpose. Given that the individual fairness regions in P have been computed, the time complexity of Algorithm B is On)), since most of the steps only require iterating over all points in P. Note that we do not need to implement Algorithm 3 in practice.
Algorithm 3: PSGENERATE
Input: set of points P, desired number of selected points k, fairness parameter a, accuracy
parameter < 1/2
Output: an instance of k-selection under partition matroid constraints w.r.t. the given instance of f-fair k-selection for the proof
Compute the set {(o, ko), (B1, ki).... ; kim) } (P, ()) using Algorithm
Let Pu {unle P} be copy of P
Let B fu B₁} be copy of B, for all B; B
P' Po U B.) > 1PP' has two distinct copies of the points that belong individual fairness ball B.}
Construct a distance function P R
ko kn > (denotes that we pick at most kn points from Po)
K = k; for all i E [m] >> [denotes that we pick at most k; points from B₁}
Let min d(x,y) y)
Let d'(u, u) 0 for all u P'
Let d' (122 Uy) = d(u, u) for all Uzz Myy E P' where v # Fu
Let d' (Uz, vy) = cō for all Ca, Uy E Pr
return (P', (PPo, To). (B1,
(Bm, km)))dd
We show that the distance function d' in Algorithm 3 is a metric distance.
Lemma 3. The distance function P x P' + R constructed in Algorithm constitutes a metric
space. (See the proof Appendix B.3
B Missing Proofs
B.1 Proof of Lemma
Proof. First, we show that the set of centers returned by Algorithm I satisfies property (1) of the individual fairness regions. For every point x E P eg denote the first center added to C such that d(z, ex) I 2a r(z). Hence, d(z, C) < d(x, cx) < 2a r(x) where the last inequality follows from
21

---

the fact that Oz marks z as covered. Next, consider the iteration of the algorithm in which a center added to C. Since is an uncovered point, its distance to any other center e' that is already in C is more than 2a r(c) 2a max(r(c), r(e') where the equality follows from the fact that centers are picked in a non-decreasing order of their fair radius. Hence, for any pair of centers in C, property (2) holds. Finally, by property (2), the balls of radius r(-) around the centers present in C are disjoint. Moreover, according to the definition of fair radius, each of the balls [B(c, r(c)) JoEC contains at least n/k points. Hence, the number of individual fairness regions is at most k.
Now we consider the time complexity of Algorithm | When generating individual faimess regions, the first step (Line 5) is to iterate over all radii to find the minimal fair radius, whose worst time complexity is (n)). The time complexity of Line 6 is obviously O(1). The final step (Line 7) requires iterating over points in ZiZ, whose time complexity is O(n). Considering the outer while loop runs at most & times, the total time complexity of Lines 5, 6, and is (nk)). O(k), and O(nk), respectively. Thus, the total time complexity for generating individual fairness regions is (nk)). L
B.2 Proof of Lemma
Proof. Let S be a set of cluster centers that is feasible w.r.t. B. For every point x E P, let cu denote the first center chosen by Algorithm such that d(x, (2) S 2a r(x). Moreover, let 8, denote the center in such that 82 E BCc,, a r(e))). Then, for any point x E P. we have
d(z, 8a) S d(x, cx) d(c,.8))
I 2a r(z) + d((c,,82)
< 20 r(x) + r((a)
1 3a r(z).
where the first inequality follows from the triangle inequality, the second inequality follows from the property (1) of individual fairness regions, the third inequality follows since 8 E B(Ca, a+ r(())). and the last inequality follows since centers are added in non-decreasing order of their fair radius in line 5 of Algorithm| I
leading to r(c.)= S r(z).
B.3 Proof of Lemma 3
Proof. Let u. U. w E (FU M) be three arbitrary points and let up, up, wp be their corresponding points from P. First, we prove that d'(u, v) = 0 < = c. If u = v, the distance d' (u, e) is set to zero by line 10. To show the other direction, if d'(u, v) = 0 then the constraint u v for the assignment in line 10 is satisfied since d(up, Up) > 0 for all u, * up (line 11) and d' (u, v) eō > 0 when up = U, and u o u (line 12). Secondly, we prove the symmetric property d' (u, v) d' (u, u). v and therefore d' (v, u) = 0 d' d'(u, v). Assume d'(u,)) v) > 0, which implies u + v. If up * vp, then by line 11 and the metric properties of d, d'(u, v) d(up,up)
If d' (u, v) = 0, then by the first part
d(Up, up) d' d'(v, u) holds. Lastly, we show that the triangle inequality d'(u, w) S d'( + + dd'(v, w) holds. If u = w then by the first property, d' d'(u, w) = 0 so the equality holds. Assume a w and consider their corresponding points up WP.
1. up = Wp then d(u,,) = =ô. up = up then d' (u, v) = d'(u, w) = =ō and therefore d' (u, w) S d' d'(u.v) d' (v, w) already holds. If up # ur, then d' (u, d(ur, up) 2 min d(z y) 2 c6. Thus, d' (u, w) S d' (u, + d' (v, w) holds.
2. If up # wp, then d' (u, w) = d(ur, wp) 2 eδ. Note that (up up and up = wp) can not hold, so consider the remaining three cases:
(a) up wp and up # up. Then d'(u d'(u, w) = d'(u, v) and d'(u, w) < d'(u, v) + d' w);
(b) up up and Up # wp. Then d'(u, w) = d' d'(v, w) and d' w) S d'(u, v) + (u, w):
(c) ur F vp and up F wp. Then d'(u, w) = d(ur, wr), d'(v, w) = d'(ur, wr) and since d(-) satisfies the triangle inequality, d' (u, w) s d' (u d'(u, w) holds.
By combining the above results, we conclude that d'(..)) is metric distance.
22

---

B.4 Proof of Theorem 3
Proof. Let MAXMINALG be a B-approximation algorithm for k-selection under partition matroid constraints for max- max-min diversification. Consider {(Pu, ko); (B,,,)),..................)))... (Bm, kn]} as the original metric space with individual fairness regions on P constructed by Algorithm [ Consider an instance of a--air k-selection on P and let be the instance of k-selection under partition matroid constraints constructed by Algorithm with input parameters P. kt and a. We show that the solution returned by MAXMINAI.G (PPo, ko), (B),), ( (Bm, km))) is (5,3)-bicriteria approximate solution of the given instance of a-fair k-selection on P.
Let SOLG be the solution returned by MAXMINALO(((P1.) ko), (B).,,) km))). Let OPT; be the optimal solution on (((Po, ko), (BI,k),..... (Bm, km)} maximizing the diversity for max-min diversification on P under partition matroid constraints. We let OPTs be the optimal solution on (P" (Po. Ko). B1......... (B m km)) }, d') from Algorithm 3 maximizzng the diversity for max-min diversification on P' under partition matroid constraints. We also let OPT, be the optimal solution on P which maximizes the diversity with individual fairness constraints satisfied.
Fairness Approximation: Given that SOLG is constructed under partition matroid constraints, for each i E [m]. [B; n SOLg| 2 1. Hence, by Lemma 2 SOLG is a (3ar) k-selection of P.
(OPT', P'). No matter what OPTa is, we can always construct COR's in P' whose diversity is equivalent to OPTs in P. We start with an initially empty set of centers CORG. In the first step, for each B B, let C denote arbitrary center in OPT n B,, and then we add the point с E B, corresponding to G; to CORG. Next, in the second step, for each op in the rest points of OPTg, we add the point o E Po corresponding to Op to COR'6- It is obvious that COR's has exactly distinet centers and the pairwise distances between COR's are the same as those between OPTg. Therefore, divnm (OPTc, P)= = div mm ( (COR'G, P'). Considering that div (OPT P') 2 divam (CO P'), we have div mm (OPTg, P) S div mm (OPT',
Diversity Approximation: We first prove that div mm (OPTa, P)
Now we assume that div mm (OPT,, P) < div mm (OPT', P¹). If there do not exist two points v', v' in OPT; that are the copies of the same point in P. then we can always find the original & points in P (which are corresponding to OPT2) whose diversity is greater than current div (OPT,, P) and equals m.mm(OPTT P'), which is a contradiction. If there exist two points u', e' in OPT that are the copies of the same point in P, then the diversity is eō given the definition of max-min diversification, which is much smaller than div.m (OPTa. P), leading to a contradiction. Therefore, div.m (OPT P)= = divmm (OPT', P').
Next, we connect the partition matroid constraints on P' with individual fairness constraints on P. By the definition of a-fairness, each point u E P must have a center in OPT, within distance at most a-r(v). Hence, for each individual fairness region B E B. (PPTyn 2 1. For each i E [m=] let e, be the copy of an arbitrary center E О in the set B,, For the remaining points in OPT,, we pick their corresponding copies in the set Po. Let OPT denote the constructed solution for the instance P'. Since OPT:, picks exactly one point from each set B,, for E [m], and exactly k h- m points from Po. OPT ez is feasible solution for max- diversification under partition matroid constraints on instance (P', (PPo, ko). kT),........ (B m, Fm,)) (,m)),cm d'). Since the pairwise distances between OPT, the same as those between OPT we can have div (OPT, P)
(OPT' P'). Considering that OPT is the optimal solution on instance (P', [(Po. To)), (B1, KT)...., (Bm, km)), ), d'), we can have div mm (OPT) P')= > div divmmOOPP : P'). Hence, we have
div.mm (OPT, P) < divmm (OPT' P') = divmmm (OPT P') S B (SOLL P). Thus, the diversity of max-min diversification under individual fairness constraints of P using SOLG is within a 3 factor of the diversity of any optimal a-fair k-scleccton of P.
B.5 Proof of Theorem
Proof. We use the same notations as those in Proof of Theorem 3 The only difference is that MAXMI- NALG is changed into MAXSUMALG, referring to 3-approximation algorithm for k-selection under partition matroid constraints for max-sum diversification. We show that the solution returned by MAX- SUMALG (((P,, ko), (B1, ki),..., (Bm, kmm) )) a (3(4 + e), 3)-birrtteria approximate solution of the given instance of a- fair k-selection on P.
23

---

Diversity Approximation: We first prove that (4+ E)
G. P'). We can get (OP P) S (OV P') through the same process shown in the same part in Proof of Theorem 3 Let us focus on the case when dOV P) < div P') occurs. In this case, there are two or more points in OPT being copies of the same point in OPT.. The extreme situation is that each point pi in OPT can always find another point P/2 in OPT G. and their original point in P is the same point. Therefore, in general situations, there are at most P whose two copies in P' are both selected.
P) 2 mi (OPT
points in
In order to obtain the diversity of the extreme situation, we now consider the basic case where there are only four points in P' that are selected, and there are only two points in P. which are the original points of the four points in P'. W.I.o.g., let EXP", be the four points in P' containing di alz, alz, d' and EXP2 be the two distinct original points in P containing d1, 0g, where of, a2 are the copies of
a1, and dg. a4 are the copies of az. From the definition, we can have d' (aaa, 22) = d' d'(ag. a44) = Ed, d'(d,, ag) = d'(ai, d'4) = d' (ab, ag)) = d' (d2, o44) = d(ai, 03), It is obvious that div (EXP2, P) = d(ai, 03), while we have div (EXP' 1, PO) = d' (ah, a/2) d' (d'g d/1) + d' (a) og)) + d' (a(4 d() +
d' d' ag) + d' (2(2 a1) = 4 div (EXP,, P) 2ed.
Now consider the situation for OPT is not extreme, ie.. there exists at least one point pi in OPT that is unable to find another point pl in OPT; satisfying d' (p/,p4) = =ò. There are two types let EXP be the 3 points in P' containing
of basic situations. W.I.ogg, in the first situation, ai d22 alz and EXP2 be the 2 distinct original points in P containing 41, 02 where ab. dg are the
copies of ag, and a/ is the only copy of a1- From the definition, we can have d' (a (2) ed, d' d'(dj, ob) = d' (a': og) = d(a 02). We can have div..s (EXP's, P') = d' (a(,, a²) + d' d'(ai, 4²}) + 2- div (EXP P) + E8 S 4- ddivms (EXP2. P) 2ed. In the second situation,
d' d' og)
let EXP2 be the 2 points in P' containing ai alg and EXP, be the 2 original points in P containing @1 02. where ai is the only copy of a1, and a/ is the only copy of d2 as well. We have d' (a(, 04) d(ai, a2)
and div (EXP/,, P') = div (EXP2, P) S 4 dEX, P) + 280.
For general OPT in P", mi (OPTg) is combination of the three basic cases mentioned above. We let ORI be the distinct original points in P which are corresponding to OPT' in P. We can have 4- div (ORI, P) + ] 2 divm=(OPT' P'). Given that there at least _ points in ORI, we have divms (ORI, P) 2 _ and we can further have (4 + =) divms (ORI, P) 2 divns(OPT''.... P"). Next, we assume |OR|| max-sum diversification under partition matroid constraints in P. We can have divm.(OPTc. P) Z div... (OPTS, P), since the addition of any other point to OPT would increase the diversity. Given that div OPT P) 2 div,ns (ORI, P), we have div (OPTg, P) 2 (ORI, P). Therefore, we can come to the conclusion that (4 + =)- div.m:(PPT. G, P) 2 div (OPT',
k > J. and we let OPT: be the optimal solution for ks-point
Through the same process as that in proof of Theorem we have
div.,. (OPT,, P) S (OVT', P') < (4 +) div (OPTs, P) S 8(4+ div... P).
Thus, the diversity of max-sum diversification under individual fairness constraints of P Pusnng SOLG is within a 8(4 + E) factor of the diversity of any optimal a-fair k-selection of P.
B.6 Proof of Theorem 5
Proof. We use the same notations as those in the proof of Theorem The only difference is that MAXMINALG is changed into SUMMINALG, referring to a 8-approximation algorithm for k-selection under partition matroid constraints for sum-min diversification. We show that the solution returned by SUMMINALO ((.P.. ko), (B1, kt).... (Bm, km.) )) is a 3)) approximate solution of the given instance of a-fair k-selection on P.
Diversity Approximation: We first prove that (4 + s)- (OPTo, P) > div (OPT', P'). We can get div (OPTg. P) < dOV a P') through the same process shown in the same part in Proof of Theorem S
Let us focus on the case when div.. (OPTa, P) < div (OPT P') occurs. In this case, there are two or more points in OPT's being copies of the same point in OPT.. We assume that there are 2 S k. Now we focus on two points a', da in OPT's satisfying d' (a', ab) zó if they exist. It can be inferred that these kinds of points contribute
distinct original points in P correesponding to OPT in p',
24

---

2(k - z)Eō to the overall diversity, since d' (a ) = d' da OPT (22) = d' a5) = Eō and there are 2(k 2) points from OPT involved in this calculation.
Let us define D = sm (OPT G= P*) - 2(k - z)εò. We notice that D does not equal the diversity of the original = points in P. This is because some points in the original points that are copied to OPT' have contributed zō to iivssOOPTc: P"), so they cannot make any other contribution to D. Let O be the optimal solution for z-point sum-min diversification under partition matroid constraints in P. From what we have discussed above, we can get D - divsm (OPTG, P).
(OPT P). Now are going to introduce lemma 6 so to compare div (OPT d P) and sm
Lemma 4. Let (P. d) be a metric space, and n = [P]. Suppose 1 < k < n is the target number of elements. Let S' be any subset of V of size S k. Then can efficiently find an S S V of size k. such that di, P) 2 siv P). (See the proof in Appendix B.7
Based on Lemma for OPT we can always find a TEMP C P of size = k. such that 4 am P) a0V P). Obviously, di (TEMP, P) I (OPT,, P), since O is the optimal solution. We can now have
div (OPT P) S 4 div (OPTo: P)
if 1 < k < n/3. Now we have
div (OPTo, PT) = D + 2(k - 2)88
- div (OPT 6: P) + 2(k 2)8ō
< 4. div ( (OPTo, ;, P) + 2(k - 2)06.
As mentioned in the proof of Theorem 4 k | Therefore, have 2(k: 2)cō s 2 2 keō S aOV P). Therefore, we have div (OPT', P() S (4 +1)+ div sm (OPT P).
Hence, we finally come to the conclusion that
P) I div (OPT',,
S (4+ (OWT
< (4 +) div.mm (SOLG, P).
Thus, the diversity of sum-min diversification under individual fairness constraints of using SOL- is within a B(4 E) factor of the diversity of any optimal a-fair k-selection of P.
B.7 Proof of Lemma 4
Proof. Let us suppose < k n/3, and let S' be set of size r < k. We may assume that 2 and so we can suppose that S' = (u1, u2, ), for 1 < < k.
Let us partition P into P2. P... where P. is the set of vertices whose closest neighbor in S is u4. Without loss of generality, assume that |Pl 2 |P 2 ... 2 |P. Also, let d, denote the minimum distance from u; to the rest of S". We consider two cases:
Case I ([P: > k): First, consider the set of points W1 := {u2, u3..... ..,, T, where T is an arbitrary set of k-r++ 1 points in P1. We claim that the diversity of W2 is at least This is because for any > 1, every point in P1 at a distance at least d./2 from u, (to see this, consider some E P:: we know that d(v, u1) < u.), by the definition of P;; thus, if d(v, w;) < d,/2, we must have d(vy u1) < de, a contradiction). Second, let v be the us that is furthest from un. Clearly, we have d(u1, v) 2 d1. Now consider the set of points W2 == {v) UT where T is any set of k - vertices in Pt. From the same argument as above, the diversity of W2 is at least /2/ Now, one of the sets above must have diversity (d1 + d2 + + dz) div (S", P)/4. This completes the argument in this case.
+d.)/2.
Case 2 ( < k < n/3): In other words, all the sets V/2 have size < k. Now, let be the smallest index for which UP. P.I 2 k. Since all the IP: are smaller than k < n n/3, we certainly have < r. Furthermore, we must have PP.+1 U....UP. Prl 2 k. Now, define W1 := {u1, U2, 2o } UT. where T is an arbitrary set of k a elements from Ps+1 U... .....UPP P. and W2 := (u.+I...., Up U elements from P1 U...U P.. By the above argument, the
where 7' is an arbitrary set of k-
diversity of W, is at least (dl + d2 + + d.)/2, and that of W2 at least (dst1 +... d.)/2. As before, one of these quantities is at least di (S', P)/
25

---

C Discussion on Error Parameter in Theorems 6
C.1 Error Parameter in Theorem 6
The algorithm used in Theorem 6 is FMMD-S from [46], which is a (5 + ( -pprroxxinntoonnn algorithm for max-min diversification under group fairness constraints running in O(mkn + m log time. Therefore, in Theorem 6 directly inherits the error parameter in FMMD-S.
C.2 Error Parameter in Theorem 7
In the proof of Theorem 4 is an accuracy parameter in Algorithm Therefore, in Theorem is the accuracy parameter in Algorithm 3 In Section is small positive constant used to control the threshold for accepting local improvements. Thus, a smaller can potentially lead to better results while incurring higher computational overhead.
C.3 Error Parameter in Theorem g
In the proof of Theorem 5 & an accuracy parameter Algorithm 3 The algorithm used in Theorem is from [6] with no other parameter involved in its approximation factor. Therefore, in Theorem is just the accuracy parameter in Algorithm
D Extended Theoretical Analysis for Max-Min Diversification
In Theorem show that the time complexity of algorithm is exponential w.r.t k as it FMMD-S 46 as a subroutine. This arises because max-min diversification with individual fairness is at least hard its partition matroid-constrained version (Theorem B3) To date, however, algorithm can simultaneously satisfy the following four requirements: (i) the solution exactly meets the partition matroid constraint; (ii) the time complexity is polynomial; (iii) the solution provides constant-factor approximation guarantee for max-min diversification; and (iv) the algorithm works in general metric spaces.
To provide different trade-offs among these requirements, we show that our algorithm can work with different algorithms for max-min min diversification with group fairness constraints. The main results summarized as follows:
1. FMMD-S [6] According to the concept of group fairness defined in 46 after executing Algorithm 2 one can directly apply FMMD-S by restricting the number of points selected each individual fairness region lie between and k + 1. The solution achieves 5-approximation while strictly satisfying group fairness constraints, as indicated in Theorem 6 However, FMMD-S relies on solving an ILP for solution computation and thus has an exponential time complexity w.r.t. k.
2. Fair-Greedy-Flow 3 According to the concept of group fairness defined BI, after executing Algorithm 2 can directly apply Fair-Greedy--Pi by pre-specifying for each individual fairness region a constant k; 2 1 such that the sum of all k; 's is equal to k. This algorithm in O(kmm²) time but only provides the number of individual fairness regions.
(m))-apprxximmtion where m is
3. MFD [25]: According to the definition of group fairness in 225. after executing Algorithm one can directly apply MFD by pre-specifying for each individual fairness region constant k; 2 such that the sum of all &; 's is equal to k. This algorithm has a near- linear time complexity of (nn) and achieves constant approximation. However, the algorithm is randomized and its solutions may not always satisfy the fairness constraints. In addition, MFD is specific to Euclidean space.
Each of these methods does not meet at least one of the four requirements. Considering the empirical performance of our algorithm, we chose the FMMD-S algorithm [66 in our implementation.
26


Reviews:
[{"review_id": "jGXowIaKPe", "reviewer": "Reviewer_NtvU", "summary": "In this paper, the authors study the problem of diversity maximization under individual fairness constraints. The objective is to select a subset of $k$ points from a dataset such that diversity is maximized while ensuring fairness, where every point has a representative within a bounded distance. The authors provide a $(O(1), 3)$ bicriteria approximation algorithm, where the representative is at most $3$ times the distance to the nearest neighbor, and diversity is a constant fraction of the optimal diversity. These algorithms leverage fairness-aware partitioning techniques and matroid-based optimization to achieve theoretical guarantees for fairness and diversity. Empirical evaluations on real-world and synthetic datasets validate their approach.", "questions": "Can the authors comment on whether diversity maximization with individual fairness constraints versus group fairness constraints is equivalent in terms of computational hardness? Or is there any reduction between these problems?", "limitations": "N/A", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths**:\n\nWhile group fairness has been well studied, individual fairness with diversity-based objectives has not been studied before. The motivation of the setting is novel and an important addition to the diversity maximization literature. The authors provide approximation algorithmic results for different diversity maximization objectives studied in the literature with individual fairness.\n\nMany prior works (on group fairness) design algorithms by reduction to partition matroids. In this work, the authors design an interesting approach of partitioning the points into individual fairness regions and then employing partition matroid methods to satisfy the constraints.\n\n**Weaknesses**:\n\nThe algorithmic novelty is limited. It would be interesting to see if there is a way to improve on the $O(1)$ guarantees. It suggests that the guarantee is because of the partition matroid, and it is not immediately clear how hard the problem is with respect to group fairness.\n\nThe computational complexity of $O(n^2)$ is certainly a challenge when scaling up to real-world datasets. It would be interesting to understand if there is a hardness result (fine-grained complexity) with regard to computational complexity.", "was_revised": true, "final_justification": "I'm happy with rebuttal response. As I asked for clarification questions, I am keeping my score (borderline accept).", "rebuttal": "We sincerely thank you for your valuable feedback and the time you dedicated to reviewing our paper! We address each of your comments point by point below.\n\n> Q1: The algorithmic novelty is limited.\n\nA1: To the best of our knowledge, our work is the first in the literature to integrate individual fairness guarantees with diversity objectives. Moreover, rather than focusing on a single diversity objective, we systematically analyze three well-established diversity functions, max-min, max-sum, and sum-min, which have each received significant attention in prior work. This broader scope requires distinct algorithmic designs, analyses and proofs tailored to the structural differences of these objectives. We therefore believe that both the problem formulation and the algorithmic contributions reflect meaningful novelty.\n\n \n\n> Q2: It would be interesting to see if there is a way to improve on the $O(1)$ guarantees.\n\nA2: We appreciate the reviewer's comment on potential improvements over the current $O(1)$ approximation guarantees. However, asymptotic improvements are not possible. We now prove that for all three diversity maximization objectives under individual fairness constraints, no polynomial-time algorithm can achieve a diversity approximation factor better than $O(1)$. The proof is similar to that in Moumoulidou et al. (2020) *Diverse Data Selection under Fairness Constraints*.\n\n**Theorem 1** There exists no polynomial-time $\\beta$-approximation algorithm for individually fair max-min diversification with $\\beta<2$, unless P=NP.\n\n*Proof Sketch.* Suppose that there exists a polynomial algorithm that approximates the diversity score of the optimal solution to individually fair max-min diversification by a factor of $\\beta<2$. Then, this algorithm could also solve the unconstrained max-min diversification problem with approximation factor $\\beta$. However, Ravi et al. (1994) *Heuristic and special case algorithms for dispersion problems* have shown that unconstrained max-min diversification cannot be approximated within a factor better than 2, through a reduction from the clique problem. Therefore, it is not possible for such an algorithm to exist.\n\nBy a similar argument, and leveraging the fact that max-sum and sum-min diversification cannot be approximated within a factor better than 2 under the planted clique conjecture (Bhaskara et al. (2016) *Linear relaxations for finding diverse elements in metric spaces*), we can also prove the following theorem:\n\n**Theorem 2** There exists no polynomial-time $\\beta$-approximation algorithm for individually fair max-sum and sum-min diversification with $\\beta<2$ under planted clique conjecture.\n\nTherefore, the unconstrained diversity maximization problems can be viewed as special cases of our setting under individual fairness constraints. This implies that our problems cannot achieve asymptotic improvements beyond the known $O(1)$ approximation barrier. Nevertheless, future work may still refine these results by establishing smaller constant-factor bounds. We will add the above two theorems and their proofs to the paper to explicitly demonstrate the hardness of our problem.\n\n\n\n> Q3: It suggests that the guarantee is because of the partition matroid, and it is not immediately clear how hard the problem is with respect to group fairness.\n\nA3: In our algorithm, the individual fairness constraint is transformed into a partition matroid constraint, and therefore, the approximation guarantees under individual fairness are directly related to those under partition matroid constraints. By definition, any solution that satisfies group fairness also satisfies the partition matroid constraint, making partition matroids a more general class, with group fairness being a specific instantiation. This implies that solving the problem under group fairness is a more specific and arguably simpler case. \n\nHowever, it is important to note that individual fairness and group fairness are not directly interchangeable: they capture fundamentally different notions of representation, and results for one do not automatically extend to the other.\n\n\n\n> Q4: The computational complexity of $O(n^2)$ is certainly a challenge when scaling up to real-world datasets. It would be interesting to understand if there is a hardness result (fine-grained complexity) with regard to computational complexity.\n\nA4: We agree that, in the current implementation of Algorithm 1 and Algorithm 2, the computational bottleneck arises from an $O(n^2 \\log n)$ time complexity. This cost is primarily incurred due to repeatedly identifying the minimum fair radius among all remaining elements (Line 4 in Algorithm 1). In our prototype implementation, we employed Python’s built-in `set` data structure and performed sorting during each iteration to identify the minimal element, which indeed leads to the stated complexity.\n\nHowever, as the reviewer correctly noted, this is not an inherent lower bound of the algorithm but rather a byproduct of our current implementation strategy. In practical systems with efficiency concerns (such as in industrial applications), more sophisticated data structures could be employed to significantly reduce the computational overhead. For example:\n\n- If we store the candidate elements in a list or array, we can sort them once at the beginning, and the subsequent set difference operations will not affect the internal order. This allows for an overall $O(n \\log ⁡n)$ time complexity.\n- Alternatively, using a min-heap or a priority queue enables extracting the minimum fair radius in $O(\\log⁡n)$ time per iteration. Since the outer loop runs at most $n$ times, this results in an improved total complexity of $O(n\\log ⁡n)$.\n\nGiven that the time complexity can theoretically be reduced, in the revised version we will optimize the implementation accordingly and add the above discussion to clarify this point (Section: **B.1 Proof of Lemma 1**).\n\n \n\n> Q5: Can the authors comment on whether diversity maximization with individual fairness constraints versus group fairness constraints is equivalent in terms of computational hardness? \n\nA5: At present, analyses of the computational hardness of diversity maximization under either group fairness or individual fairness constraints are derived from results in the unconstrained setting. Specifically, if $P \\neq NP$, then no polynomial-time algorithm can achieve an approximation factor better than 2 for max-min diversification; and under the planted clique assumption, the same hardness holds for max-sum and sum-min diversification. These results imply that, regardless of whether group fairness or individual fairness constraints are imposed, no polynomial-time algorithm is expected to surpass the factor-2 barrier. You may refer to our response to Q2, where we formally present and prove that for all three diversification objectives under individual fairness constraints, the approximation factor has a lower bound of 2.\n\nMoreover, we emphasize that after defining the fairness parameter $\\alpha$ in Definition 2, we explicitly note in Lines 152–155 that even finding a feasible solution that strictly satisfies the individual fairness constraint is itself NP-hard. This further underscores the additional difficulty of diversity maximization under individual fairness constraints.\n\n\n\n> Q6: Is there any reduction between these problems?\n\nA6: Yes, there is. The unconstrained diversity maximization problem can be seen as a special case of individually fair diversity maximization, where the fairness parameter $\\alpha$ is sufficiently large so that the fairness constraints become vacuous. A more detailed argument along this line is provided in our response to Q2.\n\n\n\nThank you again for your constructive comments!"}, {"review_id": "r6T5PwbPCE", "reviewer": "Reviewer_uok7", "summary": "The paper focused on the diversity maximization problem with the additional constraint of individual fairness based neighborhood radii as introduced in Jung et al. Three diversity maximization objectives are considered (max-min, max-sum, sum-min) and approximation bicriteria algorithms with guarantees are introduced for them.", "questions": "Please see weaknesses above.", "limitations": "No real need to discuss potential negative societal impact.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "## Strengths\n\n-The paper is mostly well-written.\n\n-I did not have a chance to look at the proofs, but the derivations do not seem trivial. \n\n## Weaknesses\n\nI think the major issues are with the motivation for the model/notion of fairness and the parameter $m$ and the runtime in Theorem 4. More details:\n\n1-The motivation of the problem is not clear. Why is this notion of fairness needed? The objectives (1-3) on page 3 are all calculated based on S, but definition 2 on page 4 is based on all of the Points in P not in S? The paper does not give any motivations for the model.  \n\n2-lines (52-57), I don’t see how the corporate recruitment example is a good motivation for additionally imposing the n/k constraint? How does it guarantee that every qualified applicant has a chance of being interviewed?\n\n3-There is an issue with Theorem 4. In particular, the run-time is exponential in k which is a big disadvantage. Further, I cannot understand the bound on the value of $m$ , is it not the case that $m \\leq k$ . This would make the result significantly weaker. If the run-time can indeed be very slow in terms of k, then I think the paper should've been clear about this. Especially, since the other objectives do not have a similar problem. \n\n4-Is the experimental section comparing against any baselines? I don’t see where the baselines are?\n\n\nMinor Points:\n\n1-‘Non-private’ line 13, replace by something like unfair instead.\n\n2-In definition 3 on page 4, for point 2. It should be just $\\gamma$ not $\\gamma \\dot \\alpha$, correct?\n\n3-What is the GMM algorithm in line 323?", "was_revised": true, "final_justification": "The authors have given a better motivation for the problem and will be explicit about the exponential dependence on $k$, this improves the quality of the submission.", "rebuttal": "We greatly appreciate your thoughtful and constructive comments! Below, we provide detailed responses to each of your points.\n\n> Q1: The motivation of the problem is not clear. Why is this notion of fairness needed? The objectives (1-3) on page 3 are all calculated based on S, but definition 2 on page 4 is based on all of the Points in P not in S? The paper does not give any motivations for the model.\n\nA1: Our motivation focuses on performing diverse data selection, where the goal is to obtain subsets that achieve both strong diversity and individual fairness. Data selection is a common and important task, but identifying such representative subsets is not trivial. Specifically, diversity seeks to maximize dissimilarity among selected items so that the subset captures a wide range of information in the dataset. Fairness, on the other hand, ensures that representation is balanced across certain features.\n\nOne application can be found in facility location problems. There, individual fairness requires that every demand point lies within a reasonable distance of some selected facility, ensuring that no individual is left underserved. At the same time, diversity encourages the selected facilities to be well-dispersed across the space, avoiding excessive concentration in one area. This illustrates how fairness and diversity capture complementary goals that must be balanced in representative selection tasks.\n\nIt is worth noting that while diversity maximization with group fairness constraints has been studied, individual fairness constraints differ in two critical ways:\n\n1. **No external group definitions are required.** Fairness regions in our setting are induced directly from data features rather than externally specified demographic attributes.\n2. **Different perspectives.** Group fairness ensures balance at the group level, but may still neglect individuals within a group. Individual fairness starts from each single data point, ensuring that all individuals are adequately represented by the selected set.\n\nWe appreciate this observation, and we will revise the introduction to emphasize these distinctions and make the motivation for our formulation more explicit.\n\n> Q2: Lines (52-57), I don’t see how the corporate recruitment example is a good motivation for additionally imposing the n/k constraint? How does it guarantee that every qualified applicant has a chance of being interviewed?\n\nA2: The corporate recruitment example provided in the manuscript does not fully align with the motivation of individual fairness in diversity maximization, as recruitment is often more naturally modeled as a ranking task rather than a representative selection problem. Therefore, we propose a more suitable example to better illustrate our motivation.\n\nA more suitable example, as discussed in our response to Q1, comes from **facility location**. In this setting, individual fairness requires that every demand point lies within a reasonable distance of some chosen facility, ensuring that no individual is left completely unserved. At the same time, diversity encourages the selected facilities to be spread out rather than concentrated in one area. The $n/k$ constraint reflects this balance: it ensures that representatives are not overly clustered and that coverage is reasonably distributed across the entire population.\n\nFor a detailed elaboration of this motivation, we kindly refer the reviewer to our response to Q1. We will revise the manuscript accordingly and replace the current example with this more suitable one.\n\n> Q3: There is an issue with Theorem 4. In particular, the run-time is exponential in *k* which is a big disadvantage. Further, I cannot understand the bound on the value of *m* , is it not the case that *m*<=*k*. This would make the result significantly weaker. If the run-time can indeed be very slow in terms of k, then I think the paper should've been clear about this. Especially, since the other objectives do not have a similar problem.\n\nA3: We agree that the exponential dependence on *k* in the runtime of Theorem 4 is a significant theoretical limitation. As noted in Lemma 1 (Lines 203–204, 522–532), we have formally shown that *m* ≤ *k*, which indeed implies that the runtime complexity is exponential in *k*—a fact that makes the computational cost appear even less desirable. \n\nThis arises because max-min diversification with individual fairness is at least as hard as the partition matroid-constrained version (Theorem 1, Line 236-239). To date, however, no algorithm is known that simultaneously (i) satisfies partition matroid constraints exactly, (ii) operates in polynomial time, and (iii) achieves a constant-factor approximation guarantee for max-min diversification in (iv) general metric spaces.\n\nSeveral representative approaches illustrate the trade-offs:\n\n- **Wang et al. (2023), Max-Min Diversification with Fairness Constraints: Exact and Approximation Algorithms**:\n  According to the definition of group fairness in that paper, after executing Algorithm 2 from our paper, one can directly apply their algorithm **FMMD-S** by restricting the number of points selected in each individual fairness region to lie between $1$ and $k-m+1$. This method achieves an $O(1)$ approximation factor while strictly satisfying group fairness constraints, but relies on solving an ILP formulation, leading to exponential runtime in *k*.\n- **Addanki et al. (2022), Improved Approximation and Scalability for Fair Max-Min Diversification**:\n  According to the definition of group fairness in that paper, after executing Algorithm 2 from our work, one can directly apply their algorithm **Fair-Greedy-Flow** by pre-specifying for each individual fairness region a constant $k_i \\geq 1$ such that the sum of all $k_i$ equals $k$. This method runs in polynomial time ($O(nkm^3)$) but only provides an $O(m)$ approximation factor.\n- **Kurkure et al. (2024), Faster Algorithms for Fair Max-Min Diversification in $ℝ^d$**:\n  According to the definition of group fairness in that paper, after executing Algorithm 2 from our work, one can directly apply their algorithm **MFD** by pre-specifying for each individual fairness region a constant $k_i \\geq 1$ such that the sum of all $k_i$ equals $k$. This method obtains near-linear runtime $O(nk)$ and constant approximation, but the algorithm is randomized and may not always strictly satisfy fairness constraints. Besides, it is only for Euclidean space.\n\nEach of these alternatives sacrifices some combination of fairness guarantees, approximation quality, runtime, or the type of metric space in which the result holds. Given these trade-offs—and considering the practical performance of our algorithm (See Figure 3)—we chose the Wang et al. algorithm for our implementation.\n\nWe acknowledge that the lack of a universally efficient and optimal algorithm for this class of problems is a limitation of our work. We will revise the manuscript in **Conclusion** (Lines 376–379) to clarify this issue and highlight the complexity aspect as an important direction for improvement.\n\n> Q4: Is the experimental section comparing against any baselines? I don’t see where the baselines are?\n\nA4: Our experiments do include baselines. Specifically, in our experimental design, to evaluate the approximation quality of our algorithm with respect to diversity, we measure the ratio between the diversity achieved by our algorithm and that achieved by the unconstrained algorithms. Thus, the unconstrained algorithms serve as baselines to illustrate the *price of fairness*, and our results confirm the effectiveness of our approach.\n\nThat said, we acknowledge that we could make the use of baselines more explicit by directly reporting additional metrics obtained from the unconstrained algorithms. As we mention in our response to Reviewer 15en’s Q3, we have added new experiments and results to highlight these comparisons, and we will incorporate these experiments into the revised version of the paper.  We believe this addition will strengthen the persuasiveness of our experimental evaluation.\n\n> Q5: ‘Non-private’ line 13, replace by something like unfair instead.\n\nA5: We agree with this point and we will replace 'Non-private' with 'unfair'.\n\n> Q6: In definition 3 on page 4, for point 2. It should be just *γ* not *γα*, correct?\n\nA6: Upon close inspection, we confirm that our use of *γα* in Definition 3 is intentional and correct. This is because we allow the parameter *α* to be greater than 1, even though *α* = 1 represents the most stringent case. This form of the definition is also consistent with prior work, including Mahabadi and Vakilian (2020)'s *Individual Fairness for k-Clustering*, Vakilian and Yalçıner (2022)'s *Improved Approximation Algorithms for Individually Fair Clustering* and Ebbens et al. (2025)'s *A Subquadratic Time Approximation Algorithm for Individually Fair k-Center*.\n\n> Q7: What is the GMM algorithm in line 323?\n\nA7: The GMM algorithm originates from the work of Gonzalez (1984), *Clustering to Minimize the Maximum Intercluster Distance*, and was later shown in Ravi et al. (1992), *Heuristic and special case algorithms for dispersion problems*, to be a 2-approximation algorithm for Max-Min diversity maximization in metric spaces. We agree that the first occurrence of the term “GMM” lacked an explicit description of the algorithm and its references. We will add the appropriate citation at Line 323 and include a description and pseudocode of the algorithm in the appendix. \n\n\n\nThank you again for your constructive comments!"}, {"review_id": "fhAsTHRvH5", "reviewer": "Reviewer_nRw7", "summary": "The paper studies a combination of diversity maximization and individual fairness in centroid clustering. Diversity maximization requires that the selected points are (in some sense) sufficiently spread out, while individual fairness requires that every point in the clustering instance should have a selected center somewhere in their vicinity. The paper gives a general framework for approximating diversity subject to approximate individual fairness. This framework guarantees bi-criteria approximations to both.", "questions": "None currently", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "In general this seems like a solid paper. Both diversity maximization and individual fairness are problems that are somewhat frequently studied, and combining them seems natural. There is a lot of work on bi-criteria optimization for standard clustering objectives (such as k-center or k-means), so why not design bi-criteria optimization algorithms for diversity maximization. In its techniques the paper is very similar to those previous works (which is not really surprising as for instance k-center and Max-Min Diversification are closely related, with the tight $2$-approximations for either essentially being the same algorithm). For instance, the construction of the individual fairness regions here is essentially the same as what is done in ``A Subquadratic Time Approximation Algorithm for Individually\nFair k-Center'' by Ebbens et al. at AISTATS this year (I briefly thought that one might be able to directly apply their algorithm here as well, but this is not as easy, as the algorithm of Ebbens et al. can select strictly less than $k$ points and filling after these points is crucial) and I think a bit more discussion on why previous algorithms fail would have been nice.\n\nIn general, while I think that the paper is solid, I am not entirely sure if it is strong enough for NeurIPS. In particular, the paper does not feel very significant to me, and more like another twist on an already mostly established formula. I am willing to be convinced by the other reviewers here, though.\n\nMinor Comments:\n- Line 50: \"an individual notion of fairness\" reads a bit weird to me\n- Line 50-51: You should probably note that such a clustering does not always exist\n- Line 54: How does this example related to clustering? While this is a \"subset-selection\" problem it is not really a clustering problem. Also I am not really sure you want your measures of diversity in such a setting.\n- Our Contributions: \\alpha is undefined here\n- Line 109: Technically the group fairness notion studied by paper [10] is the nearly equivalent to individual fairness as studied in this paper, see \"Proportional fairness in clustering: A social choice perspective\", Kellerhals and Peters, NeurIPS 2024\n- \"seminal work\" might be too high praise\n- Line 123: \\mapsto should be \\to\n- Line 125: \"to denote the subset of points.\" what do you mean by \"the subset of points\"?\n- Line 131 onwards: You do not really need P in the definitions, also missing {} around the u(s)\n- Line 152: You should briefly mention that alpha = 2 can be achieved and that this is tight.\n- I found the statements of Theorems 1, 2,3 to be somewhat unclean, maybe they could be written nicer.\n- Line 531: Mathmode around n/k missing", "was_revised": true, "final_justification": "Thank you to the authors for the very detailed rebuttal (in fact I think it is too detailed). However, the level of detail still does not entirely convince me that the paper is strong enough for NeurIPS. Just combining two known concepts does not necessarily make for a good/well-motivated paper, and at the moment this paper mostly seems derivate/not strong enough for NeurIPS to me.", "rebuttal": "Thank you for the positive and constructive comments! Here, we offer comprehensive responses to each of your points.\n\n> Q1:  For instance, the construction of the individual fairness regions here is essentially the same as what is done in ``A Subquadratic Time Approximation Algorithm for Individually Fair k-Center'' by Ebbens et al. at AISTATS this year and I think a bit more discussion on why previous algorithms fail would have been nice.\n\nA1: We appreciate the reviewer’s insightful comment. Indeed, we have carefully considered whether the algorithm proposed by previous work could be directly applied to our setting. However, due to the fundamental differences between our problem and the standard individually fair k-center formulation, we believe such a direct application is not feasible.\n\nThe core distinction lies in the objective function. Prior works on fair clustering, including Ebbens et al., focus on minimizing a clustering-based loss, which inherently depends not only on the selected points but also on the structure of the entire dataset. In contrast, diversity maximization objectives—such as max-min, max-sum, or sum-min—depend solely on the selected subset. This creates a fundamental computational divergence between clustering and diversity maximization.\n\nMoreover, diversity objectives exhibit different and often opposite monotonicity properties with respect to the number of selected points. For instance, max-min diversity is typically non-increasing, max-sum diversity is strictly increasing, and sum-min diversity shows no clear monotonic trend. On the other hand, most clustering objectives, including those studied by Ebbens et al., are non-increasing with the number of centers, and are framed as minimization problems. This misalignment in objective structure and monotonicity behavior makes the design and analysis of approximation algorithms for diversity maximization under fairness constraints significantly more challenging.\n\nTherefore, although some high-level conceptual parallels exist, applying previous fair clustering algorithms would require entirely new analytical frameworks and cannot be done in a black-box manner. We hope this clarification highlights the novelty and technical contributions of our approach.\n\n> Q2: In particular, the paper does not feel very significant to me, and more like another twist on an already mostly established formula.\n\nA2: As mentioned in our response to A1, our problem setting is meaningfully distinct from prior works, although we do draw conceptual inspiration from the broader literature on individual fairness.\n\nWe would like to emphasize that our contribution is not merely a minor modification of an existing framework. For each diversity objective considered in our paper, we designed approximation algorithms with rigorously proven guarantees, and each proof was carefully tailored to the unique structural properties of the respective objective function. These proofs were developed independently and are not based on prior templates or proof techniques from the literature.\n\nFor instance:\n\n- In the Max-Min objective, we leverage the *non-strictly decreasing* property of the diversity function to repeatedly apply proof by contradiction in bounding the approximation factor.\n- In the Max-Sum objective, rather than analyzing sums over arbitrary pairs, we reformulate the analysis in terms of minimal four-point units, which enables a tractable and effective upper bound.\n- In the Sum-Min objective, we address the lack of monotonicity by reducing the analysis to a special case that admits a form of monotonicity proven in our Lemma 4, allowing for a meaningful approximation guarantee.\n\nWe believe these contributions—both in problem formulation and in the technical development of distinct analysis tools—demonstrate the novelty and significance of our work.\n\n> Q3: Line 50: \"an individual notion of fairness\" reads a bit weird to me\n\nA3: The phrase *“an individual notion of fairness”* was used intentionally, following its usage in Vakilian and Yalçıner (2022), *Improved Approximation Algorithms for Individually Fair Clustering*. As our work shares a similar focus on fairness at the individual level we adopted this phrasing to align with established terminology in the literature.\n\n> Q4: Line 50-51: You should probably note that such a clustering does not always exist\n\nA4: In Definition 2 (Lines 150–155) of our paper, we explicitly state that determining whether such a clustering exists is NP-hard. Our intention in the earlier discussion was not to assert the universal existence of such a clustering, but rather to introduce a natural and intuitive formulation of the problem that can help readers grasp the motivation and definition of our setting.\n\n> Q5: Line 54: How does this example related to clustering? While this is a \"subset-selection\" problem it is not really a clustering problem. Also I am not really sure you want your measures of diversity in such a setting.\n\nA5: Upon reviewing our manuscript, we acknowledge that the description in Line 49-54 was inaccurate. The example provided is indeed a subset-selection problem, not a clustering problem. We will revise the phrasing in this part to refer to it as a diversity maximization problem instead of a clustering problem. \n\nWe also recognize that the corporate recruitment example is not the best fit for illustrating diversity maximization under individual fairness, since recruitment is often better modeled as a ranking task. A more appropriate example is the facility location problem, where one must determine a set of facility locations from a large geographical area. For a more detailed justification of this example, we kindly refer the reviewer to our responses to Reviewer uok7’s Q1 and Q2. We will revise the manuscript accordingly and replace the current example with this more suitable one. \n\n> Q6: Our Contributions: \\alpha is undefined here\n\nA6: Thank you for pointing this out. The parameter α was indeed not defined when first mentioned in the \"Our Contributions\" section. In the revised version, we will give intuitive and informal explanations in Introduction, describing α as the fairness parameter that controls the allowed relaxation of individual fairness constraints.\n\n> Q7: Line 109: Technically the group fairness notion studied by paper [10] is the nearly equivalent to individual fairness as studied in this paper\n\nA7: Thank you for the correction. You are absolutely right that [10] aligns more closely with the definition of individual fairness. We will revise the manuscript to relocate [10] alongside the reference you suggested—*Proportional Fairness in Clustering: A Social Choice Perspective* (Kellerhals and Peters, NeurIPS 2024)—in the section where we describe individual fairness more accurately.\n\n> Q8: Line 110: \"seminal work\" might be too high praise\n\nA8: We described the cited work as “seminal” because it was the first to formally introduce the notion of individual fairness. Similar phrasing can be found in Vakilian and Yalçıner (2022), *Improved Approximation Algorithms for Individually Fair Clustering*, where their introduction refers to the work of Chierichetti et al. (2017) *Fair clustering through fairlets*, which is the first work introducing the concept of fair clustering, in a comparable manner. Nonetheless, if the wording feels overly strong, we are open to softening it in the revision.\n\n> Q9: Line 123: \\mapsto should be \\to\n\nA9: After reviewing several related works, we agree with this point and we will replace '\\mapsto' with '\\to'.\n\n> Q10: Line 125: \"to denote the subset of points.\" what do you mean by \"the subset of points\"? Line 131 onwards: You do not really need P in the definitions, also missing {} around the u(s)\n\nA10: Regarding the missing `{}`, we believe our notation is acceptable and consistent with prior literature. For instance, Bhaskara et al. (2016) in their NIPS paper *Linear Relaxations for Finding Diverse Elements in Metric Spaces* adopt a similar notation in their definition of diversity functions.\n\nAs for the use of $P$ in our definitions, we intentionally specify that $S \\subseteq P$ and include $P$ when defining the diversity function. This is because in the proofs of Theorems 1, 2, and 3, we construct a new metric space $P'$, and it becomes important to clearly distinguish between the original and modified ground sets. Explicitly stating the ground set $P$ and subset $S$ helps clarify the domain on which diversity is measured and avoids confusion when comparing diversity values across different spaces. Therefore, we prefer to keep the current formulation.\n\n> Q11: Line 152: You should briefly mention that alpha = 2 can be achieved and that this is tight.\n\nA11: We agree that it is helpful to include this information. In Jung et al. (2019), *Service in Your Neighborhood: Fairness in Center Location*, it is shown that an approximation factor of $\\alpha = 2$ can be achieved and that this bound is tight. We will add a brief remark to clarify this in the revised version in order to further discuss feasibility.\n\n> Q12: I found the statements of Theorems 1, 2, 3 to be somewhat unclean, maybe they could be written nicer.\n\nA12: Thank you for the suggestion. We understand that the current statements of Theorems 1, 2, and 3 may appear slightly verbose or indirect. We will revise them to improve clarity and conciseness. For example, Theorem 1 can be rewritten as:\n\n*Suppose that there exists a $\\beta$-approximation algorithm for $k$-selection under partition matroid constraints for max-min diversification. Then, there exists a $(\\beta,3)$-bicriteria approximation for $\\alpha$-fair $k$-selection for max-min diversification.*\n\nWe will apply similar improvements to Theorems 2 and 3 in the revised version.\n\nQ13: Line 531: Mathmode around n/k missing\n\nA13: We agree this is a missing, and we will replace 'n/k' with '$n/k$'.\n\n\n\nThank you again for your constructive comments!"}, {"review_id": "h0yGISXEkj", "reviewer": "Reviewer_15en", "summary": "The paper discusses the problem of finding a diverse set of k points from a given point set in a metric space. There are three ways of quantifying diversity:\n1. max-min diversification: maximize the minimum distance between any pair of selected points,\n2. max-sum diversification: maximize the sum of pairwise distances between selected points, and \n3. sum-min diversification: maximize the sum of the minimum distances from each selected point to its nearest neighbor among the other selected points. \n\nThese problems are well-studied in the literature, and an approximation lower bound of 2 is known for them. Approximation algorithms closely matching the lower bound are also known. This paper explores these problems with an additional constraint that every point in the point set has at least one of its (n/k)-nearest neighbors as its “representative” among the chosen k points. This property is called the individually fair property.\n\nThe paper gives approximation algorithms for the three diversity problem with the added individually fair constraint. The nature of the approximation algorithm is a bicriteria (a, b) approximation, where a is the approximation guarantee for the diversity objective, and b is the factor by which the individually fair radius is exceeded. \n\nThe algorithm uses the following reduction-based idea:\n- First, the set of points is partitioned into (approximate) individually fair regions.\n- Then, a known approximation algorithm for the diversity problem under the partition matroid is used on the point set and the partition to obtain the bicriteria approximation algorithm.\n\nExperiments are performed and observations are made about the algorithms with and without the individually fair constraint.", "questions": "Comments: \n- (lines 61 - 75): Bicriteria approximation has not been defined in the paper yet. It is only defined later. So, it is difficult to read. Also, what purpose does \\alpha serve in these statements?\n- Other questions are mentioned in the summary and strengths and weaknesses.", "limitations": "Yes. The paper presents theoretical results that do not have any potential negative societal impact.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- Theoretical results about two opposing objectives (diversity and individual fairness) are good to know. The problem formulation makes sense and may be useful.\n\n\nWeaknesses:\n- Since the major part of this work is theoretical, the lack of approximation lower bound statements to support some of the approximation upper bounds stands out and can be seen as a weakness.\n- Discussions related to checking whether there is a feasible solution for the individually fair problem seem to be missing. It'll be good to have this discussion.\n- The experimental results are designed to observe properties of the problem and the suggested algorithm. Some experiments that can motivate the problem formulation can help to make the paper more interesting.", "was_revised": true, "final_justification": "I remain positive about the paper after the rebuttal. The authors agree to discuss some of the points I raised in the final version. I will maintain my original score.", "rebuttal": "We are truly grateful for your insightful feedback and the time you spent evaluating our work. Below, we provide detailed responses to each of your comments.\n\n> Q1: Since the major part of this work is theoretical, the lack of approximation lower bound statements to support some of the approximation upper bounds stands out and can be seen as a weakness.\n\nA1: Thank you for pointing this out. We have addressed this concern in our response to Reviewer NtvU’s Q2, where we prove that for all three diversity maximization objectives under individual fairness constraints, the approximation lower bound cannot be better than 2. We will include the corresponding lower-bound statements and proofs in the revised manuscript to explicitly demonstrate the hardness of our problem.\n\n\n\n> Q2: Discussions related to checking whether there is a feasible solution for the individually fair problem seem to be missing. It'll be good to have this discussion.\n\nA2: We appreciate the reviewer’s suggestion. In the current version, we briefly mention the NP-hardness of deciding whether there exists a solution that strictly satisfies individual fairness after Definition 2 (Lines 152–155). However, we agree that this important issue deserves more explicit discussion. As also pointed out by Reviewer nRw7, it is known that when $\\alpha = 2$, a feasible solution always exists, and this bound is tight (see Jung et al. 2019). We will revise the paragraph following Definition 2 to clearly explain the computational hardness of checking feasibility, and to emphasize the significance of the $\\alpha = 2$ threshold, which guarantees feasibility.\n\n\n\n> Q3: The experimental results are designed to observe properties of the problem and the suggested algorithm. Some experiments that can motivate the problem formulation can help to make the paper more interesting.\n\nA3: Thank you for your constructive comment. We acknowledge that although our original experiments were designed to demonstrate the effectiveness of our algorithm, their role in motivating the problem formulation was not explicitly conveyed. \n\nWe would also like to take this opportunity to reiterate the central motivation of our work: individual fairness in representative selection. That is, our goal is to ensure that each unselected point is adequately represented by the selected set, preventing certain regions of the data from being disproportionately neglected. \n\nTo further support the motivation, we have added a new set of experiments to emphasize how fairness constraints influence the solution quality in alignment with the motivation behind our problem definition.\n\nSpecifically, we compare the solutions obtained under unconstrained diversity maximization with those obtained under individual fairness constraints, across three canonical diversity objectives. For each case, we evaluate the solutions using three complementary metrics:\n\n1. **Fairness performance** $⁡\\alpha_{\\max}$: fairness performance, which has been defined in the paper (Section: *Measures* in *Experiment*, Lines 339–340).\n2. **Max Distance**: the largest distance between any unselected point and its nearest selected point.\n3. **Average Distance**: the average distance from each unselected point to its nearest selected point.\n\nSmaller values of these metrics indicate better individual-level representativeness of the selected set, thereby aligning with the goals of individual fairness.\n\nThe table below reports partial results from our experiments on the CelebA dataset, with selection sizes $k = 5, 10, 20$. For each diversity objective (Max-Min, Max-Sum, Sum-Min), we compare the algorithms for the unconstrained and fairness-constrained problems using the three metrics mentioned above. These results illustrate how fairness constraints improve individual coverage, which directly supports the motivation for our fairness-aware formulation. All algorithms and other settings used here are the same as those employed in the experimental section of the paper.\n\n| k    | Metric           | Max-Min (Unconstrained) | Max-Min (Fairness) | Max-Sum (Unconstrained) | Max-Sum (Fairness) | Sum-Min (Unconstrained) | Sum-Min (Fairness) |\n| ---- | ---------------- | ----------------------- | ------------------ | ----------------------- | ------------------ | ----------------------- | ------------------ |\n| 5    | Actual α         | 1.18                    | **1.05**           | 1.30                    | **1.15**           | 1.17                    | **1.10**           |\n|      | Max Distance     | 2019.70                 | **1987.75**        | 2100.38                 | **2075.56**        | **2029.92**             | 2039.88            |\n|      | Average Distance | 1306.51                 | **1193.54**        | 1406.64                 | **1291.87**        | 1297.98                 | **1235.41**        |\n| 10   | Actual α         | 1.27                    | **1.10**           | 2.16                    | **1.24**           | 1.26                    | **1.13**           |\n|      | Max Distance     | 1951.72                 | **1926.83**        | 2359.95                 | **2023.46**        | 1959.41                 | **1939.41**        |\n|      | Average Distance | 1303.03                 | **1173.17**        | 1941.29                 | **1270.74**        | 1293.79                 | **1211.71**        |\n| 20   | Actual α         | 1.35                    | **1.18**           | 2.121                   | **1.32**           | 1.35                    | **1.25**           |\n|      | Max Distance     | 1822.25                 | **1771.05**        | 2167.25                 | **1899.74**        | **1833.73**             | 1849.33            |\n|      | Average Distance | 1296.87                 | **1156.07**        | 1766.35                 | **1264.50**        | 1295.00                 | **1220.42**        |\n\nThe table above demonstrates that across all diversity objectives and selection sizes, the fairness-constrained algorithms consistently outperform or match their unconstrained counterparts in terms of both fairness and representation quality. These consistent improvements support our central argument that enforcing fairness constraints enhances individual coverage without sacrificing overall selection quality.\n\nDue to the space and time constraints of the rebuttal, we only report partial results here. In the revised version of the paper, we will provide the full experimental settings, including results across all datasets mentioned in the manuscript and for a wider range of $k$ values, along the three metrics above. This extended analysis will further highlight our motivation and confirm that our algorithms indeed improve individual fairness compared to their unconstrained counterparts.\n\n\n\n> Q4: Bicriteria approximation has not been defined in the paper yet. It is only defined later. So, it is difficult to read. Also, what purpose does \\alpha serve in these statements?\n\nA4: Thank you for highlighting this point. The parameter $\\alpha$ controls the level of individual fairness — specifically, it allows for relaxing the strict fairness constraint in order to achieve approximate feasibility. To improve readability, we will add intuitive and informal explanations of both $\\alpha$ and bicriteria approximation in **Introduction**, so that readers can better understand their role before encountering the formal definitions.\n\n\n\nThank you again for your constructive comments!"}]

Author rebuttal:

Meta-review: This paper addresses diversity maximization under individual fairness constraints, which is a novel and timely extension of prior fairness work. Reviewers found the formulation clear and the approximation guarantees interesting, and they appreciated the contributions as relevant to the fairness/diversity literature. However, concerns were raised regarding:

•	Motivation and applications, which need to be made clearer and illustrated with stronger examples.

•	Computational complexity, especially the exponential dependence in Theorem 4, which should be explicitly discussed.

•	Positioning against prior work and comparisons to baselines, which are currently limited.

Overall, the paper makes a meaningful contribution, though it would benefit from clearer motivation, computational complexity discussion in the final version. We strongly encourage authors to address reviewers' feedback in the final version of their paper.
Decision: Accept (poster)