# Max-Min Diversification with Fairness Constraints:
Exact and Approximation Algorithms

Yanhao Wang East China Normal University<EMAIL_ADDRESS>Michael
Mathioudakis University of Helsinki<EMAIL_ADDRESS>Jia Li
East China Normal University<EMAIL_ADDRESS>Francesco Fabbri Spotify.
<EMAIL_ADDRESS>
###### Abstract

Diversity maximization aims to select a diverse and representative subset of
items from a large dataset. It is a fundamental optimization task that finds
applications in data summarization, feature selection, web search, recommender
systems, and elsewhere. However, in a setting where data items are associated
with different groups according to sensitive attributes like sex or race, it
is possible that algorithmic solutions for this task, if left unchecked, will
under- or over-represent some of the groups. Therefore, we are motivated to
address the problem of _max-min diversification with fairness constraints_ ,
aiming to select $k$ items to maximize the minimum distance between any pair
of selected items while ensuring that the number of items selected from each
group falls within predefined lower and upper bounds. In this work, we propose
an exact algorithm based on integer linear programming that is suitable for
small datasets as well as a $\frac{1-\varepsilon}{5}$-approximation algorithm
for any $\varepsilon\in(0,1)$ that scales to large datasets. Extensive
experiments on real-world datasets demonstrate the superior performance of our
proposed algorithms over existing ones.

Keywords: max-min diversification, algorithmic fairness

##  1 Introduction

In recent years, algorithms have been increasingly used for data-driven
automated decision-making in many domains of everyday life. This has raised
concerns about the possibility that algorithms may produce unfair and
discriminatory decisions for specific population groups, particularly in
sensitive socio-computational domains such as voting, hiring, banking,
education, and criminal justice [25, 12]. To alleviate such concerns, there
has been a lot of research devoted to incorporating fairness into the
algorithms for automated decision tasks, including classification [14],
clustering [10], ranking [32, 24], matching [28], and data summarization [8,
20].

This paper considers the diversity maximization problem and addresses its
fairness-aware variant. The problem consists in selecting a diverse subset of
items from a given dataset and is encountered in data summarization [8, 23],
web search [2], recommendation [21], feature selection [31], and elsewhere
[34]. Existing literature on the problem of diversity maximization primarily
focuses on two objectives, namely _max-min diversification_ (MMD), which aims
to maximize the minimum distance between any pair of selected items, and _max-
sum diversification_ (MSD), which seeks to maximize the sum of pairwise
distances between selected items. As shown in Figure 1, MMD tends to cover the
data range uniformly, while MSD tends to pick “outliers” and may include
highly similar items in the solution. Since the notion of diversity captured
by MMD better represents the property that data summarization, feature
selection, and many other tasks target with their solutions, we will only
consider MMD in this paper. To be precise, given a set $V$ of $n$ items in a
metric space and a positive integer $k\leq n$, MMD asks for a size-$k$ subset
$S$ of $V$ to maximize the minimum pairwise distance within $S$.

In particular, we study the _fair max-min diversification_ (FMMD) problem, a
variant of MMD that aims not only to maximize the diversity measure defined
above but also to guarantee the satisfaction of group fairness constraints as
described below. Let all the items in $V$ be divided into $C$ disjoint groups
$V_{1},\ldots,V_{C}$ by a sensitive attribute such as sex or race. To ensure a
fair representation, the number of items selected from each group $V_{c}$,
where $c\in[1,\ldots,C]$, is limited to be between lower and upper bounds
specified as input. This definition of group fairness constraints captures and
generalizes several existing notions of _fairness_ for groups, including
proportional representation [7, 17], equal representation [20, 19], and
statistical parity [14, 33], and has been widely used in optimization problems
such as top-$k$ ranking [9], submodular maximization [17], and multiwinner
voting [7].

(a) MMD

(b) MSD

Figure 1: An illustration of max-min diversification (MMD) vs. max-sum
diversification (MSD). The items in the solutions are marked in blue color.

###  1.1 Related Work

Erkut [15] proved that the MMD problem is NP-hard in metric spaces. Ravi _et
al._ [26] proposed a $\frac{1}{2}$-approximation greedy algorithm [16] for MMD
and proved that no polynomial algorithm could achieve a better approximation
factor unless P=NP. Recently, many different algorithms have been proposed for
MMD in various settings. Indyk _et al._ [18] proposed a
$\frac{1}{3}$-approximation distributed algorithm for MMD based on the notion
of _coresets_. Drosou and Pitoura [13] designed a
$\frac{b-1}{2b^{2}}$-approximation cover tree-based algorithm for MMD on
dynamic data, where $b$ is the base of the cover tree. Ceccarello _et al._ [6]
proposed $(\frac{1}{2}-\varepsilon)$-approximate MapReduce and streaming
algorithms for MMD in metric spaces of bounded doubling dimension. Borassi _et
al._ [5] proposed a sliding-window algorithm for MMD. Nevertheless, none of
the above algorithms are applicable to FMMD because they cannot guarantee the
fulfillment of fairness constraints.

Moumoulidou _et al._ [23] first proposed approximation algorithms for the fair
variant of MMD. Addanki _et al._ [1] improved the approximation ratios of the
algorithms in [23]. Wang _et al._ [30] proposed two streaming algorithms for
the fair variant of MMD. However, these algorithms work for exact-size group
fairness constraints, a special case of our bounded-size group fairness
constraints. Moreover, as shown empirically, these algorithms provide lower-
quality solutions than ours.

Besides MMD, many other optimization problems have similar group fairness-
aware variants – e.g., determinantal point processes [8], $k$-centers [20, 11,
19], top-$k$ ranking [9], submodular maximization [17, 29], and multiwinner
voting [7]. However, since their objectives differ from MMD, the algorithms
proposed for their fair variants are not directly applicable to FMMD.

###  1.2 Our Results

The main results of this paper are two novel algorithms for the _fair max-min
diversification_ (FMMD) problem, which selects a size-$k$ subset $S$ from a
dataset $V$ that maximizes the diversity value while satisfying group-fairness
constraints.

We first propose FMMD-E, an exact algorithm that is suitable for solving FMMD
on small datasets, despite the NP-hardness of the problem. This algorithm
exploits the connection between the MMD and maximum independent set (MIS)
problems. It formulates FMMD as the problem of finding an independent set of
vertices with group fairness constraints on an undirected graph. Then, the
optimal solution of FMMD can be obtained in $O(n^{k}\log n)$ time by solving
the reduced problem via integer-linear programming (ILP).

Since FMMD-E cannot scale to large datasets, we propose FMMD-S, a more
scalable approximation algorithm for FMMD. Specifically, for any
$\varepsilon\in(0,1)$, FMMD-S provides $\frac{1-\varepsilon}{5}$-approximate
solutions for FMMD in $O\big{(}Ckn+C^{k}\log{\frac{1}{\varepsilon}}\big{)}$
time. Under the assumptions that $k=o(\log{n})$ and $C=O(1)$, the time
complexity of FMMD-S is reduced to
$O\big{(}n(k+\log{\frac{1}{\varepsilon}})\big{)}$. The basic idea of FMMD-S
is, in the first step, to limit the computation to a considerably smaller
subset of the original dataset (i.e., _coreset_) by running the greedy
algorithm [16, 26] and, in the second step, to use an ILP-based method similar
to FMMD-E to obtain an approximate solution to FMMD from the subset.

Finally, we compare the performance of our algorithms with the state-of-the-
art algorithms in [23, 1, 30] for the FMMD problem on real-world datasets. The
results show that _i)_ FMMD-E provides exact solutions in reasonable time on
small datasets (e.g., $n=1,000$); _ii)_ FMMD-S returns solutions of higher
quality than existing approximation algorithms in comparable time while
scaling to large datasets with millions of items.

##  2 Preliminaries

In this section, we first formally define the FMMD problem, a fairness-aware
variant of max-min diversification (MMD), and then provide its hardness
result.

#### Max-Min Diversification (MMD).

Let $V$ be a set of $n$ items and $d:V\times V\rightarrow\mathbb{R}_{\geq 0}$
be a distance metric that captures the dissimilarities between items in $V$.
We remind that, by definition, $d(\cdot,\cdot)$ satisfies the following
properties for any $u,v,w\in V$: _i)_ $d(u,v)=0\Leftrightarrow u=v$ (identity
of indiscernibles); _ii)_ $d(u,v)=d(v,u)$ (symmetry); _iii)_
$d(u,v)+d(v,w)\geq d(u,w)$ (triangle inequality). For MMD, the diversity value
$div(S)$ of a subset $S\subseteq V$ is defined as the minimum among all
pairwise distances between distinct items in $S$ – i.e., $div(S)=\min_{u,v\in
S\,:\,u\neq v}d(u,v)$. Given a set $V$, a distance function $d(\cdot,\cdot)$,
and a positive integer $k\leq n$, the MMD problem asks for a size-$k$ subset
$S$ of $V$ such that $div(S)$ is maximized.

#### Fair Max-Min Diversification (FMMD).

Let the set $V$ be divided into $C$ disjoint groups $V_{1},\ldots,V_{C}$ by a
sensitive categorical attribute, such as sex or race. For FMMD, the fairness-
aware variant of MMD, the group fairness constraints restrict the selection of
items from each group $V_{c}$ for $c\in[C]$ so that the number of items
selected from $V_{c}$ lies within a range of values from $l_{c}$ to $h_{c}$
(both inclusive). Meanwhile, it also requires that the total number of
selected items is $k$. Formally, the collection $\mathcal{F}$ of all feasible
solutions for FMMD is

$\mathcal{F}=\\{S\subseteq V:|S|=k\wedge l_{c}\leq|S\cap V_{c}|\leq
h_{c},\forall c\in[C]\\}$

and, to discard from consideration trivially empty sets $\mathcal{F}$, we will
further assume that $l_{c}\leq h_{c}\leq|V_{c}|$ and $\sum_{c=1}^{C}l_{c}\leq
k\leq\sum_{c=1}^{C}h_{c}$. The FMMD problem asks for a subset $S$ of $V$ so
that $S$ satisfies the group fairness constraints (i.e., $S\in\mathcal{F}$)
and $div(S)$ is maximized, or formally,
$S^{*}=\operatorname*{arg\,max}_{S\in\mathcal{F}}{div(S)}$, where $S^{*}$ and
$\mathtt{OPT}=div(S^{*})$ denote the optimal solution of FMMD and its
diversity value, respectively.

#### Hardness of FMMD.

By using a reduction from the Clique problem, MMD is proven to be NP-hard for
general metric spaces and cannot be approximated within any factor greater
than $\frac{1}{2}$ unless P=NP [15, 26]. Nevertheless, a greedy algorithm
provides the best possible $\frac{1}{2}$-approximate solution in $O(kn)$ time
[16]. Although the greedy algorithm does not work for FMMD directly, as it may
provide solutions that do not fall within $\mathcal{F}$ (i.e., are not
“fair”), it will be used as a subroutine for our FMMD-S algorithm in Section
3.2 for data reduction. Since MMD is a special case of FMMD when $C=1$ and
$l_{1}\leq k\leq h_{1}$, the hardness result for MMD can be generalized to
FMMD as follows:

###### Theorem 2.1

FMMD is NP-hard and cannot be approximated by a factor of
$\frac{1}{2}+\varepsilon$ for any parameter $\varepsilon>0$ unless P=NP.

##  3 Algorithms

In this section, we describe our proposed algorithms for FMMD. First, we
propose FMMD-E, an exact algorithm that runs in $O(n^{k}\log n)$ time (Section
3.1). Second, we propose FMMD-S, a $\frac{1-\varepsilon}{5}$-approximation
algorithm that runs in $O\big{(}Ckn+C^{k}\log{\frac{1}{\varepsilon}}\big{)}$
time for any error parameter $\varepsilon\in(0,1)$ (Section 3.2).

###  3.1 An Exact ILP-Based Algorithm

(a) FMMD

(b) FIS

Figure 2: Example for the reduction from Fair Max-Min Diversification (FMMD)
to Fair Independent Set (FIS) on a dataset with $n=10$ points and $C=2$ groups
in blue and red. An FMMD instance with $k=5$, $l_{c}=2$ and $h_{c}=3$ for
$c=1,2$ is reduced to an FIS instance where a fair independent set of vertices
is represented by triangles.

To build an exact algorithm for FMMD, we use ideas similar to [3] for the
reduction from MMD to maximum independent set (MIS). Given the set of feasible
solutions $\mathcal{F}$ and a positive real number $\delta$, the decision
version of FMMD asks whether there is a set $S\subseteq V$ such that
$S\in\mathcal{F}$ and $div(S)\geq\delta$. Given an instance of the FMMD
decision problem, we build an undirected graph $G=(V,E)$ as follows: the set
of vertices in $G$ is identical to $V$ and there is an edge between two
vertices $u,v\in V$ if and only if $d(u,v)<\delta$. We remind that a vertex
set $S$ is called an _independent set_ iff no two vertices in $S$ are
adjacent. Moreover, we define the _Fair Independent Set_ (FIS) problem that
determines whether there exists an independent vertex set $S\in\mathcal{F}$ on
the graph $G$. Based on the above definitions, the lemma below asserts the
equivalence between FMMD and FIS.

###### Lemma 3.1

FMMD is equivalent to FIS.

  * Proof.

In the one direction, assume that the answer to FMMD is ‘ _yes_ ’ – i.e.,
there is a subset $S\in\mathcal{F}$ of $V$ with $div(S)\geq\delta$. Then, we
have $d(u,v)\geq\delta$ for any $u,v\in S$. Thus, by construction, there is no
edge $(u,v)\in E$, and $S$ is an independent vertex set of $G$. Therefore, the
answer to FIS is ‘ _yes_ ’ as well. In the opposite direction, assume that the
answer to FIS is ‘ _yes_ ’ – i.e., $S\in\mathcal{F}$ is an independent set. By
definition, there is no edge between any of its vertices in $G$, which by
construction means that $d(u,v)\geq\delta$ for any $u,v\in S$ and, therefore,
we have $div(S)\geq\delta$ for the given $S\in\mathcal{F}$. Therefore, the
answer to FMMD is also ‘ _yes_ ’. We thus prove that the answer to FMMD is ‘
_yes_ ’ if and only if the answer to FIS is ‘ _yes_ ’, which concludes the
proof.

Additionally, we have two observations for FMMD, which are easy to verify from
its definition.

######  Fact 1 (Monotonicity)

If there exists a set $S\in\mathcal{F}$ with $div(S)\geq\delta$, then such a
set will exist for any $\delta^{\prime}\leq\delta$; If there does not exist
any set $S\in\mathcal{F}$ with $div(S)\geq\delta$, then such a set will not
exist for any $\delta^{\prime}\geq\delta$.

######  Fact 2 (Discontinuity)

The optimal diversity value $\mathtt{OPT}$ for FMMD is always equal to the
distance $d(u,v)$ between some pair of items $u,v\in V$.

From all the above results, the following theorem asserts that FMMD is
reducible to FIS.

###### Theorem 3.1

An exact solution of FMMD is obtained by solving $O(\log{n})$ FIS instances.

  * Proof.

Let us consider the following algorithm. First, compute and sort the distances
between all pairs of items in $V$. Then, use a binary search on the sorted
array of pairwise distances to find the largest $d^{*}$ such that the answer
to its corresponding FIS instance is ‘ _yes_ ’. The binary search finds
$d^{*}$ in $O(\log{n})$ steps, as the number of pairwise distances is
$O(n^{2})$. And it holds that $div(S^{*})\geq d^{*}$ from Lemma 3.1.
Observation 1 guarantees that there does not exist any $S\in\mathcal{F}$ with
$div(S)>d^{*}$ due to the maximality of $d^{*}$. Observation 2 ensures that
$d^{*}$ is exactly equal to $\mathtt{OPT}$. Thus, the above procedure
identifies the exact solution to FMMD.

#### The ILP Formulation of FMMD.

In light of Theorem 3.1, what remains to obtain an exact algorithm for FMMD is
to design an exact algorithm for FIS. We note that FIS without fairness
constraints is equivalent to the _maximum independent set_ (MIS) problem. We
thus adapt the edge-based integer-linear programming (ILP) formulation of MIS
by adding fairness constraints to define an FIS instance, as shown in Eq.
3.1–3.5.

(3.1) $\displaystyle\max\quad$ $\displaystyle z=\sum_{i=1}^{n}x_{i}$ (3.2)
$\displaystyle\mathrm{s.t.}\quad$ $\displaystyle x_{i}+x_{j}\leq
1,\forall(v_{i},v_{j})\in E$ (3.3) $\displaystyle\sum_{i=1}^{n}x_{i}\leq k$
(3.4) $\displaystyle l_{c}\leq\sum_{v_{i}\in V_{c}}x_{i}\leq h_{c},\forall
c\in[C]$ (3.5) $\displaystyle x_{i}\in\\{0,1\\},\forall i\in[n]$

where $x_{i}$ is a binary variable to indicate whether $v_{i}\in V$ is
included in the solution or not, the objective function in Eq. 3.1 and the
first constraint in Eq. 3.2 are the same as the edge-based ILP formulation of
MIS, the second constraint in Eq. 3.3 limits the solution size to at most $k$,
and the third constraint in Eq. 3.4 is on the upper and lower bounds of the
number of items chosen from each group $V_{c}$. By solving the ILP in Eq.
3.1–3.5 optimally, we will either find a fair independent set $S=\\{v_{i}\in
V:x_{i}=1,i\in[n]\\}$ of $G$ if $z=k$ or confirm that there does not exist
such a set if $z<k$.

Algorithm 1 FMMD-E

0: Dataset $V=\bigcup_{c=1}^{C}V_{c}$ with $n=|V|$; lower and upper bounds
$l_{c},h_{c}\in\mathbb{Z}^{+}$ for $c\in[C]$; size constraint
$k\in\mathbb{Z}^{+}$.

0: A set $S^{*}\subseteq V$ such that $S^{*}\in\mathcal{F}$.

1: Compute the distances of all pairs of items in $V$ and sort them
ascendingly as $D[1,\ldots,\frac{n(n-1)}{2}]$

2: Let $L\leftarrow 1$, $H\leftarrow\frac{n(n-1)}{2}$,
$cur\leftarrow\frac{L+H}{2}$, $S^{*}\leftarrow\emptyset$

3: while $H>L$ do

4: Build an undirected graph $G=(V,E)$ where $E=\\{(u,v)\in V\times
V\;|\;d(u,v)<D[cur]\\}$

5: Compute the solution $\mathbf{x}$ of the ILP in Eq. 3.1–3.5

6: Find a set $S=\\{v_{i}\in V:x_{i}=1,i\in[n]\\}$ based on $\mathbf{x}$

7: if $|S|=k$ then

8: If $div(S)>div(S^{*})$ or $S^{*}=\emptyset$, then $S^{*}\leftarrow S$

9: Let $L\leftarrow cur+1$ and $cur\leftarrow\frac{L+H}{2}$

10: else

11: Let $H\leftarrow cur-1$ and $cur\leftarrow\frac{L+H}{2}$

12: return $S^{*}$

#### Algorithm Description and Complexity.

By combining the constructive proof of Theorem 3.1 and the ILP formulation of
FMMD, we obtain FMMD-E, an exact algorithm for FMMD, as presented in Algorithm
1. First, it computes the distances of all $\frac{n(n-1)}{2}$ pairs of
distinct items in $V$ in $O(n^{2})$ steps and sorts them in ascending order in
an array $D[1,\ldots,\frac{n(n-1)}{2}]$ in $O(n^{2}\log n)$ steps. Then, a
binary search is performed on $D$ to find $\mathtt{OPT}$ in $O(\log n)$ steps.
For each guess $D[cur]$ of $\mathtt{OPT}$, it builds an undirected graph $G$
in $O(n^{2})$ steps and finds a set $S$ by solving the ILP in Eq. 3.1–3.5 in
$\binom{n}{k}=O(n^{k})$ steps. If $|S|=k$, then $S\in\mathcal{F}$ and
$div(S)\geq D[cur]$. In this case, the search space is narrowed to the upper
half to check whether there is a better solution. Otherwise, or if $|S|<k$,
then $\mathtt{OPT}<D[cur]$ and the search space is narrowed to the lower half.
Finally, when the binary search is terminated, the algorithm has found the
exact solution $S^{*}$ to FMMD. The time complexity of FMMD-E is $O(n^{k}\log
n)$. Moreover, since $|D|=|E|=O(n^{2})$, its space complexity is $O(n^{2})$.

###  3.2 A More Scalable Approximation Algorithm

Algorithm 2 FMMD-S

0: Dataset $V=\bigcup_{c=1}^{C}V_{c}$ with $n=|V|$; lower and upper bounds
$l_{c},h_{c}\in\mathbb{Z}^{+}$ for $c\in[C]$; size constraint
$k\in\mathbb{Z}^{+}$; error parameter $\varepsilon\in(0,1)$.

0: A set $S\subseteq V$ such that $S\in\mathcal{F}$.

1: Pick an arbitrary item $u_{1}$ from $V$ and set $U=\\{u_{1}\\}$

2: for $i\leftarrow 2,\ldots,k$ do

3: $u_{i}\leftarrow\operatorname*{arg\,max}_{v\in V}\min_{u\in U}d(u,v)$ and
$U\leftarrow U\cup\\{u_{i}\\}$

4: Set $U_{c}\leftarrow V_{c}\cap U$, $d^{\prime}\leftarrow 2\cdot div(U)$

5: repeat

6: for $c\leftarrow 1,\ldots,C$ do

7: while $|U_{c}|<k$ and there exists some item $v\in V_{c}$ such that
$div(U_{c}\cup\\{v\\})\geq d^{\prime}$ do

8: $u^{\prime}_{c}\leftarrow\operatorname*{arg\,max}_{v\in V_{c}}\min_{u\in
U_{c}}d(u,v)$

9: $U_{c}\leftarrow U_{c}\cup\\{u^{\prime}_{c}\\}$

10: Build an undirected graph $G=(V^{\prime},E)$, where
$V^{\prime}=\bigcup_{c}U_{c}$ and $E=\\{(u,v)\in V^{\prime}\times
V^{\prime}\;|\;d(u,v)<\frac{d^{\prime}}{2}\\}$

11: Compute the solution $\mathbf{x}$ of the ILP in Eq. 3.1–3.5

12: Find a set $S=\\{v_{i}\in V:x_{i}=1,i\in[n]\\}$ based on $\mathbf{x}$

13: if $|S|<k$ then

14: $S\leftarrow\emptyset$ and $d^{\prime}\leftarrow(1-\varepsilon)\cdot
d^{\prime}$

15: until $S\neq\emptyset$

16: return $S$

The main drawback of FMMD-E is that it cannot handle large datasets due to
exponential complexity. Standard optimization libraries, such as
CPLEX111www.ibm.com/products/ilog-cplex-optimization-studio and
Gurobi222www.gurobi.com/products/gurobi-optimizer/, can only solve ILPs with
up to several thousand variables optimally in a reasonable time. A natural
approach to addressing this challenge is to identify a “ _coreset_ ”, i.e., a
small subset of the original dataset on which the exact algorithm is run to
look for approximate solutions. Formally, a subset $V^{\prime}\subseteq V$ is
called an $\alpha$-coreset ($0\leq\alpha\leq 1$) of $V$ for FMMD if
$\mathtt{OPT}[V^{\prime}]\geq\alpha\cdot\mathtt{OPT}$, where
$\mathtt{OPT}[V^{\prime}]$ is the optimal diversity value for FMMD on
$V^{\prime}$.

It now remains to answer _i)_ how such a coreset is built and _ii)_ what
approximation factor is obtained. For _i)_ , we are inspired by the notion of
_composable coresets_ [31, 18] for MMD in streaming and distributed settings.
The basic idea is first to partition the dataset and run the greedy algorithm
of [16] on each partition to obtain a partial solution and then compute a
final solution from the union of partial solutions. In the context of FMMD,
the dataset is naturally divided into $C$ groups. Thus, we first find a
solution from each group, then consider the union of all group-specific
solutions as our _coreset_ , and finally use FMMD-E to obtain a solution from
the coreset, which is feasible since the coreset size is small. We refer to
the resulting algorithm as FMMD-S. For _ii)_ , we prove that the obtained
solution offers an approximation factor of $\frac{1-\varepsilon}{5}$ for any
$\varepsilon\in(0,1)$.

#### Algorithm Description.

FMMD-S is described in Algorithm 2. Initially, it invokes the greedy algorithm
on $V$ without fairness constraints to compute an initial solution $U$ (Lines
1-3). Note that the greedy algorithm is $\frac{1}{2}$-approximate for MMD, and
any feasible solution of FMMD must also be feasible for MMD. Therefore, the
optimal diversity $\mathtt{OPT}$ of FMMD is bounded by $2\cdot div(U)$.
Subsequently, the algorithm divides $U$ by group into $U_{1},\ldots,U_{C}$ and
guesses $\mathtt{OPT}$ as its upper bound $d^{\prime}=2\cdot div(U)$ (Line 4).
For each $c\in[C]$, it runs the greedy algorithm to add new items from $V_{c}$
to $U_{c}$ until $|U_{c}|=k$ or there does not exist any $v\in V_{c}$ to make
$div(U_{c}\cup\\{v\\})\geq d^{\prime}$ (Lines 5-9). At this point, each
$U_{c}$ is a partial group-specific solution, and the union
$V^{\prime}=\bigcup_{c}U_{c}$ of partial solutions is the _coreset_. Next,
using a similar procedure to FMMD-E, it builds a graph $G$ on $V^{\prime}$
with diversity threshold $\frac{d^{\prime}}{2}$ and solves the ILP of Eq.
3.1–3.5 on $G$ to obtain a solution $S$ (Lines 11-12). Finally, if $|S|=k$, we
have got a solution $S\in\mathcal{F}$ with $div(S)\geq\frac{d^{\prime}}{2}$
and $S$ will be returned as the final solution; otherwise, $d^{\prime}$ is
decreased by a factor of $1-\varepsilon$, where $\varepsilon\in(0,1)$ is an
error parameter, and the above procedure is executed again for the smaller
$d^{\prime}$ until a feasible solution $S$ is found (Lines 13-16).

#### Theoretical Analysis.

Next, we give the complexity and approximation factor of FMMD-S.

###### Theorem 3.2

FMMD-S is a $\frac{1-\varepsilon}{5}$-approximation algorithm for FMMD running
in $O\big{(}Ckn+C^{k}\log{\frac{1}{\varepsilon}}\big{)}$ time.

  * Proof.

If there is any set $S^{\prime}\subseteq V^{\prime}$ s.t.
$S^{\prime}\in\mathcal{F}$ and $div(S^{\prime})\geq\frac{d^{\prime}}{2}$, then
FMMD-S identifies such $S^{\prime}$ (Line 12) from the exact solution of the
ILP in Eq. 3.1–3.5. In addition, since the greedy algorithm (Lines 1-3) is
$\frac{1}{2}$-approximate [26], the initial value of $d^{\prime}$ is at least
$2\cdot\frac{\mathtt{OPT}}{2}=\mathtt{OPT}>\frac{2}{5}\cdot\mathtt{OPT}$.
Therefore, to prove the approximation factor, it suffices to show that there
exists some $S^{\prime}\subseteq V^{\prime}$ s.t. $S^{\prime}\in\mathcal{F}$
and $div(S^{\prime})\geq\frac{d^{\prime}}{2}$ when
$d^{\prime}\in[\frac{2(1-\varepsilon)}{5}\cdot\mathtt{OPT},\frac{2}{5}\cdot\mathtt{OPT}]$.

Towards this end, we next construct such a set $S^{\prime}$ from $V^{\prime}$.
Let $S^{*}$ be the optimal solution for FMMD on $V$, and $S^{*}_{c}=S^{*}\cap
V_{c}$ be its subset from group $c$. First, we initialize
$S^{\prime}=\emptyset$. Then, we consider two cases for different groups. We
consider first the groups of Case #1 in arbitrary order, then those of Case #2
in arbitrary order, and select $|S^{*}_{c}|$ items from each group $c$ into
$S^{\prime}$.

Case #1 ($|U_{c}|<k$): Let $f:V_{c}\rightarrow U_{c}$ map each item $v\in
V_{c}$ to its nearest neighbor $f(v)$ in $U_{c}$. Note that the condition in
Line 7 ensures that $d(v,u)<d^{\prime}$ for any $v\in V_{c}$ and $u\in U_{c}$.
For each item $s_{c,i}\in S^{*}_{c}$, we add item $f(s_{c,i})$ into
$S^{\prime}$. We now show that the added items are distinct. Indeed, if
$f(s_{c,i})\equiv f(s_{c,j})$ for $i\neq j$, then the triangle inequality
would give $d(s_{c,i},s_{c,j})\leq
d(s_{c,i},f(s_{c,i}))+d(s_{c,j},f(s_{c,j}))=d(s_{c,i},f(s_{c,i}))+d(s_{c,j},f(s_{c,i}))<2\cdot
d^{\prime}\leq\frac{4}{5}\cdot\mathtt{OPT}<\mathtt{OPT}$; however, at the same
time we have $d(s_{c,i},s_{c,j})\geq\mathtt{OPT}$ because $s_{c,i},s_{c,j}\in
S^{*}$, which leads to a contradiction. Moreover, because we have identified
for each $s_{c,i}\in S^{*}_{c}$ one distinct item in $U_{c}$, we have
$|U_{c}|\geq|S^{*}_{c}|$. After processing all the groups in Case #1, we have
$d(f(s^{*}_{i}),f(s^{*}_{j}))\geq
d(s^{*}_{i},s^{*}_{j})-d(s^{*}_{i},f(s^{*}_{i}))-d(s^{*}_{j},f(s^{*}_{j}))>\mathtt{OPT}-2d^{\prime}\geq\frac{\mathtt{OPT}}{5}$
for any $f(s^{*}_{i}),f(s^{*}_{j})\in S^{\prime}$ and thus
$div(S^{\prime})>\frac{\mathtt{OPT}}{5}$.

Case #2 ($|U_{c}|=k$): Let $g:U_{c}\rightarrow S^{\prime}$ map each item $u\in
U_{c}$ to its nearest neighbor $g(u)$ in the current instance of $S^{\prime}$.
We remove from $U_{c}$ every $u\in U_{c}$ with
$d(u,g(u))<\frac{d^{\prime}}{2}$. Because the condition of Line 7 ensures
$d(u_{c,i},u_{c,j})\geq d^{\prime}$ for any $i\neq j$, there is at most one
item removed for each item in $S^{\prime}$ – otherwise, the triangle
inequality would give $d(u_{c,i},u_{c,j})<d^{\prime}$, thus leading to a
contradiction. Therefore, at least $k-|S^{\prime}|$ items remain in $U_{c}$.
Moreover, $|S^{*}_{c}|\leq k-|S^{\prime}|$ because $S^{\prime}$ always
contains the same number of items from each considered group as $S^{*}$
throughout the construction process. We pick $|S^{*}_{c}|$ items from the
remaining ones and add them to $S^{\prime}$. After this operation, we still
have
$div(S^{\prime})\geq\frac{d^{\prime}}{2}\geq\frac{1-\varepsilon}{5}\cdot\mathtt{OPT}$
since our earlier removal of items from $U_{c}$ ensured
$d(u_{c,i},g(u_{c,i}))\geq\frac{d^{\prime}}{2}$ for each added $u_{c,i}$.
Finally, after processing all groups in Case #2, we get a set $S^{\prime}$
that contains the same number of items from each group $c\in[C]$ as $S^{*}$,
which implies that $S^{\prime}\in\mathcal{F}$, and
$div(S^{\prime})\geq\frac{1-\varepsilon}{5}\cdot\mathtt{OPT}$. Therefore, we
conclude that FMMD-S is a $\frac{1-\varepsilon}{5}$-approximation algorithm
for FMMD.

Since it takes $O(nk)$ time to compute $U$ as well as $U_{c}$ for each
$c\in[C]$, the total time to compute $V^{\prime}$ is $O(Ckn)$ and
$|V^{\prime}|\leq Ck$. Then, the time to solve the ILP in Eq. 3.1–3.5 for
FMMD-S is $O(C^{k})$ because there are at most $\binom{Ck}{k}=O(C^{k})$
possible solutions to consider. Moreover, the number of iterations for
$d^{\prime}$ is $O(\log{\frac{1}{\varepsilon}})$ since the ratio between the
first and last values of $d^{\prime}$ is $O(1)$. Thus, the time complexity of
FMMD-S is $O\big{(}Ckn+C^{k}\log{\frac{1}{\varepsilon}}\big{)}$. When
$k=o(\log{n})$ and $C=O(1)$, its time complexity is reduced to
$O\big{(}n(k+\log{\frac{1}{\varepsilon}})\big{)}$. Additionally, its space
complexity is $O(n+C^{2}k^{2})$ since the number of edges in $G$ is
$O(C^{2}k^{2})$.

##  4 Experimental Evaluation

###  4.1 Experimental Setup

In this section, we conduct extensive experiments to evaluate the performance
of our proposed algorithms, i.e., FMMD-E and FMMD-S. We compare them with the
state-of-the-art FMMD algorithms, including FairSwap, FairFlow, and FairGMM in
[23], FairGreedyFlow in [1], and SFDM1 and SFDM2 in [30]. We implemented all
the above algorithms in Python 3 using the NetworkX library for building and
manipulating graphs and the Gurobi optimizer for solving ILPs. All the
experiments were carried out on a desktop with an Intel Core i5-9500 3.0GHz
processor and 32GB RAM running Ubuntu 20.04.3 LTS. Each algorithm was run on a
single thread. All data and code are publicly available at
https://osf.io/te34m/.

We use four public real-world datasets listed in Table 1, where $dim$ is the
dimensionality of the feature vector. The detailed information and
preprocessing procedures on each dataset are described in Appendix A. The
fairness constraints in our experiments are defined according to the
_proportional representation_ [7, 17]: For each group $c\in[C]$, we set
$l_{c}=\max(1,(1-\alpha)k\cdot\frac{|V_{c}|}{n})$ and
$h_{c}=(1+\alpha)k\cdot\frac{|V_{c}|}{n}$ with $\alpha=0.2$ in FMMD-E and
FMMD-S and $k_{c}=\lceil k\cdot\frac{|V_{c}|}{n}\rceil$ or $\lfloor
k\cdot\frac{|V_{c}|}{n}\rfloor$ in all other algorithms. All the algorithms
were executed ten times in each experiment. We report the average running time
and average diversity value of the solutions provided by each algorithm. We
use ‘N/A’ to indicate that an algorithm either does not find a solution within
one day or does not work when $C>2$ (i.e., FairSwap and SFDM1). In the
preliminary experiments (see Appendix B), we find that the solution quality of
FMMD-S hardly improves when $\varepsilon$ is decreased below $0.05$ and so we
fix $\varepsilon=0.05$ for FMMD-S in all the remaining experiments.

Table 1: Statistics of datasets used in our experiments Dataset | Group | $C$ | $n$ | $dim$ | Distance Metric
---|---|---|---|---|---
Adult | Sex | 2 | 48,842 | 6 | $l_{2}$-distance
Race | 5
S+R | 10
CelebA | Sex | 2 | 202,599 | 25,088 | $l_{1}$-distance
Age | 2
S+A | 4
Census | Sex | 2 | 2,426,116 | 25 | $l_{1}$-distance
Age | 7
S+A | 14
Twitter | Sex | 3 | 18,836 | 1,024 | Angular distance
Table 2: Diversity values of the solutions returned by different algorithms on small datasets for solution size $k=10$. The optimums $\mathtt{OPT}^{*}$ without fairness constraints are reported to show “the price of fairness”. Dataset | Group | FairSwap | FairFlow | FairGMM | FairGreedyFlow | SFDM1 | SFDM2 | FMMD-E | FMMD-S | $\mathtt{OPT}^{*}$
---|---|---|---|---|---|---|---|---|---|---
Adult | Sex | 4.51 | 3.24 | 4.81 | 2.18 | 4.03 | 4.18 | 5.30 | 4.64 | 5.30
Race | N/A | 1.73 | N/A | 1.33 | N/A | 2.83 | 4.54 | 4.01
S+R | N/A | 0.84 | N/A | 0.99 | N/A | 2.04 | 3.12 | 2.88
CelebA | Sex | 101457.3 | 55540.7 | 127354.6 | 46266.9 | 94873.3 | 93216.6 | 129818.2 | 106959.3 | 129871.5
Age | 110098.1 | 54649.6 | 127871.2 | 46312.3 | 102762.9 | 91578.2 | 129871.5 | 116701.6
S+A | N/A | 42412.7 | N/A | 39967.2 | N/A | 88026.7 | 127974.6 | 108055.3
Census | Sex | 28.4 | 15.8 | 29.8 | 14.7 | 27.2 | 28.0 | 34.0 | 30.3 | 35.0
Age | N/A | 7.6 | N/A | 9.3 | N/A | 15.7 | 34.0 | 30.3
Twitter | Sex | N/A | 1.23 | 1.44 | 1.23 | N/A | 1.39 | 1.51 | 1.46 | 1.51

(a) Adult (Sex)

(b) Adult (Race)

(c) Adult (S+R)

(d) CelebA (Sex)

(e) CelebA (Age)

(f) CelebA (S+A)

(g) Census (Sex)

(h) Census (Age)

(i) Census (S+A)

(j) Twitter (Sex)

Figure 3: Diversity values of the solutions of different algorithms with
varying solution size $k$ on small datasets.

(a) Adult (Sex)

(b) Adult (Race)

(c) Adult (S+R)

(d) CelebA (Sex)

(e) CelebA (Age)

(f) CelebA (S+A)

(g) Census (Sex)

(h) Census (Age)

(i) Census (S+A)

(j) Twitter (Sex)

Figure 4: Running time of different algorithms with varying solution size $k$
on small datasets.

(a) Adult (Sex)

(b) Adult (Race)

(c) Adult (S+R)

(d) CelebA (Sex)

(e) CelebA (Age)

(f) CelebA (S+A)

(g) Census (Sex)

(h) Census (Age)

(i) Census (S+A)

(j) Twitter (Sex)

Figure 5: Diversity values of the solutions of different algorithms with
varying solution size $k$ on full datasets.

(a) Adult (Sex)

(b) Adult (Race)

(c) Adult (S+R)

(d) CelebA (Sex)

(e) CelebA (Age)

(f) CelebA (S+A)

(g) Census (Sex)

(h) Census (Age)

(i) Census (S+A)

(j) Twitter (Sex)

Figure 6: Running time of different algorithms with varying solution size $k$
on full datasets.

###  4.2 Experimental Results

Table 2 shows the diversity achieved by different algorithms on “small”
datasets, i.e., datasets that were obtained by sampling 1,000 items uniformly
at random from each full dataset. Figures 3–4 illustrate the performance of
different algorithms on small datasets with varying $k$. Note that FairSwap
and SFDM1 are specific for the case of $C=2$ and FairGMM fails to finish
within one day when $C>3$ or $k>10$ since it has to enumerate $\binom{kC}{k}$
sets for solution computation. They are ignored in subsequent tables and
figures when they cannot provide valid solutions.

In general, FMMD-E always provides optimal solutions for FMMD within the time
limit (i.e., 24 hours) when $n=1,000$. The _price of fairness_ , measured by
the decrease in diversity due to the fairness constraints, is marginal on all
datasets except _Adult_ with $C\geq 5$. FMMD-S shows much higher solution
quality (up to $3.9\times$ greater in diversity value) than all approximation
algorithms except FairGMM. Although FairGMM sometimes provides slightly better
solutions than FMMD-S, it runs more than two orders of magnitude slower.
Moreover, the diversity values of all algorithms drop with $k$ because $div$
is a monotonically non-increasing function. The running time is independent of
$k$ for FMMD-E, grows exponentially with $k$ for FairGMM, and increases
linearly with $k$ for FMMD-S and other algorithms, which all follow from their
time complexities.

Table 3: Results of different algorithms on full datasets for solution size $k=50$. FairGMM and FMMD-E are omitted because they cannot provide any solution within the time limit (i.e., 24 hours). Dataset | Group | FairSwap | FairFlow | FairGreedyFlow | SFDM1 | SFDM2 | FMMD-S
---|---|---|---|---|---|---|---
diversity | time(s) | diversity | time(s) | diversity | time(s) | diversity | time(s) | diversity | time(s) | diversity | time(s)
Adult | Sex | 2.55 | 28.45 | 2.10 | 26.47 | 1.46 | 99.61 | 2.86 | 8.17 | 3.22 | 13.71 | 3.56 | 46.38
Race | N/A | 1.43 | 28.47 | 0.78 | 91.24 | N/A | 2.86 | 15.81 | 3.56 | 48.10
S+R | N/A | 0.99 | 32.64 | 0.50 | 148.12 | N/A | 2.55 | 23.35 | 3.61 | 45.51
CelebA | Sex | 125865.8 | 3093.9 | 101303.9 | 2624.1 | 57696.8 | 3558.0 | 128450.2 | 1473.4 | 117342.5 | 1354.4 | 123639.0 | 4536.4
Age | 112387.6 | 4141.2 | 74679.4 | 2598.8 | 55470.0 | 2260.8 | 126446.9 | 1024.0 | 121056.9 | 1222.3 | 113798.5 | 4626.6
S+A | N/A | 29278.4 | 2589.5 | 34066.4 | 3871.3 | N/A | 118598.7 | 1141.7 | 129866.3 | 4752.5
Census | Sex | 22.8 | 1533.3 | 16.8 | 1250.4 | N/A | 22.3 | 328.7 | 24.4 | 459.14 | 28.6 | 3268.8
Age | N/A | 5.2 | 1461.5 | N/A | N/A | 12.5 | 662.76 | 16.0 | 2728.2
S+A | N/A | 3.4 | 1723.5 | N/A | N/A | 11.1 | 170.98 | 15.0 | 9224.8
Twitter | Sex | N/A | 1.08 | 120.85 | 1.04 | 783.7 | N/A | 1.33 | 85.56 | 1.38 | 208.52

(a) Synthetic ($n=1,000$)

(b) Synthetic ($C=2$)

(c) Synthetic ($C=10$)

Figure 7: Results of different algorithms by varying the number $C$ of groups
and dataset size $n$ for solution size $k=20$. Since FMMD-E does not provide
any solution within the time limit on datasets with $n>1,000$, FairGMM does
not provide any solution within the time limit for $k=20$, and FairSwap and
SFDM1 cannot work with $C>2$, they are not plotted in these cases.

Table 3 presents the diversity values and running time of different algorithms
for solution size $k=50$ on all the full datasets. The performance of
different algorithms by varying the solution size $k$ from $10$ to $100$ on
full datasets (with all the items) is presented in Figures 5–6. In general,
the running time of all algorithms increases substantially with $n$ and $dim$.
FairGMM and FMMD-E fail to finish within one day and thus are omitted from
Table 3. FMMD-S provides better solutions (up to $7.2\times$ higher in
diversity value) than all the baselines in most cases. The only exception is
that FMMD-S shows slightly lower solution quality than FairSwap and SFDM1 on
_CelebA_ when $C=2$. This is because of the extremely high dimensionality of
_CelebA_ ($d=25,088$), where the distances between different pairs of points
are less distinguishable. In such cases, the thresholding method in FMMD-S is
inferior to the local search methods in FairSwap and SFDM1. Moreover, the time
efficiency of FMMD-S is lower than the baselines, as solving ILPs is often
time-consuming. Nevertheless, on _Census_ , i.e., the largest dataset with
more than two million items, FMMD-S still finishes the computation within 3
hours.

To evaluate the scalability of different algorithms, we vary the number $C$ of
groups and the number $n$ of points on synthetic datasets. In particular, each
dataset consists of ten two-dimensional Gaussian isotropic blobs with random
centers in $[-10,10]^{2}$ and identity covariance matrices. Each point is
assigned to one of the $C$ groups uniformly at random. The Euclidean distance
is used as the distance metric. For fixed $C=2$ or $10$, we obtain six
datasets with $n=10^{2},10^{3},\ldots,10^{7}$; and for fixed $n=1,000$, ten
datasets with $C=2,4,\ldots,20$.

The performance of different algorithms by varying $n$ and $C$ on synthetic
datasets for solution size $k=20$ is presented in Figure 7. In terms of
solution quality, the diversity values are steady for FMMD-E and FMMD-S but
significantly drop for all other algorithms when $C$ increases. In terms of
efficiency, the running time of FMMD-E is hardly affected by $C$. Other
algorithms run slower when $C$ is larger. Nevertheless, FMMD-S runs faster
than any other algorithm when $C\geq 8$, and its advantages in time efficiency
become more significant with increasing $C$. Finally, all algorithms’
diversity values and running time grow with the dataset size $n$. FMMD-E
cannot scale to large datasets due to its exponential time complexity. All in
all, FMMD-S outperforms all the other approximation algorithms in terms of
solution quality for different $C$ or $n$, and its advantages become more
apparent when $C$ or $n$ is larger. These results confirm the scalability of
FMMD-S concerning the group size $C$ and dataset size $n$.

##  5 Conclusion

We investigated the problem of max-min diversification with fairness
constraints (FMMD) in this paper. We proposed an exact ILP-based algorithm for
this problem on small datasets. We further designed a scalable
$\frac{1-\varepsilon}{5}$-approximation algorithm, where
$\varepsilon\in(0,1)$, on massive datasets based on our exact algorithm and
the notion of _coresets_. Extensive experimental results on four real-world
datasets confirmed the effectiveness, efficiency, and scalability of our
proposed algorithms.

While a step forward in both theoretical and experimental aspects of the
algorithms for the fair variant of diversity maximization, our work leaves
many open problems for future exploration. A natural question is whether there
is any polynomial-time $O(1)$-approximation algorithm for FMMD, since our
FMMD-S algorithm has an approximation factor of $\frac{1-\varepsilon}{5}$ but
runs in polynomial time only when $C=O(1)$ and $k=o(\log{n})$, whereas the
best-known polynomial-time algorithm in [1] only achieves an approximation
factor of $\frac{1}{C+1}$. Moreover, it would also be interesting to study the
fairness-aware variants of other diversity measures (e.g., the ones in [18,
4]).

## References

  * [1] R. Addanki, A. McGregor, A. Meliou, and Z. Moumoulidou. Improved approximation and scalability for fair max-min diversification. In _ICDT_ , pp. 7:1–7:21, 2022.
  * [2] R. Agrawal, S. Gollapudi, A. Halverson, and S. Ieong. Diversifying search results. In _WSDM_ , pp. 5–14, 2009.
  * [3] T. Akagi, T. Araki, T. Horiyama, S. Nakano, Y. Okamoto, Y. Otachi, T. Saitoh, R. Uehara, T. Uno, and K. Wasa. Exact algorithms for the max-min dispersion problem. In _FAW_ , pp. 263–272, 2018.
  * [4] A. Bhaskara, M. Ghadiri, V. S. Mirrokni, and O. Svensson. Linear relaxations for finding diverse elements in metric spaces. In _NIPS_ , pp. 4098–4106, 2016.
  * [5] M. Borassi, A. Epasto, S. Lattanzi, S. Vassilvitskii, and M. Zadimoghaddam. Better sliding window algorithms to maximize subadditive and diversity objectives. In _PODS_ , pp. 254–268, 2019.
  * [6] M. Ceccarello, A. Pietracaprina, G. Pucci, and E. Upfal. Mapreduce and streaming algorithms for diversity maximization in metric spaces of bounded doubling dimension. _Proc. VLDB Endow._ , 10:5 (2017), pp. 469–480.
  * [7] L. E. Celis, L. Huang, and N. K. Vishnoi. Multiwinner voting with fairness constraints. In _IJCAI_ , pp. 144–151, 2018.
  * [8] L. E. Celis, V. Keswani, D. Straszak, A. Deshpande, T. Kathuria, and N. K. Vishnoi. Fair and diverse DPP-based data summarization. In _ICML_ , pp. 715–724, 2018.
  * [9] L. E. Celis, D. Straszak, and N. K. Vishnoi. Ranking with fairness constraints. In _ICALP_ , pp. 28:1–28:15, 2018.
  * [10] F. Chierichetti, R. Kumar, S. Lattanzi, and S. Vassilvitskii. Fair clustering through fairlets. In _NIPS_ , pp. 5029–5037, 2017.
  * [11] A. Chiplunkar, S. Kale, and S. N. Ramamoorthy. How to solve fair k-center in massive data models. In _ICML_ , pp. 1877–1886, 2020.
  * [12] A. Chouldechova and A. Roth. A snapshot of the frontiers of fairness in machine learning. _Commun. ACM_ , 63:5 (2020), pp. 82–89.
  * [13] M. Drosou and E. Pitoura. Diverse set selection over dynamic data. _IEEE Trans. Knowl. Data Eng._ , 26:5 (2014), pp. 1102–1116.
  * [14] C. Dwork, M. Hardt, T. Pitassi, O. Reingold, and R. S. Zemel. Fairness through awareness. In _ITCS_ , pp. 214–226, 2012.
  * [15] E. Erkut. The discrete p-dispersion problem. _Eur. J. Oper. Res._ , 46:1 (1990), pp. 48–60.
  * [16] T. F. Gonzalez. Clustering to minimize the maximum intercluster distance. _Theor. Comput. Sci._ , 38 (1985), pp. 293–306.
  * [17] M. E. Halabi, S. Mitrović, A. Norouzi-Fard, J. Tardos, and J. M. Tarnawski. Fairness in streaming submodular maximization: Algorithms and hardness. In _NeurIPS_ , pp. 13609–13622, 2020.
  * [18] P. Indyk, S. Mahabadi, M. Mahdian, and V. S. Mirrokni. Composable core-sets for diversity and coverage maximization. In _PODS_ , pp. 100–108, 2014.
  * [19] M. Jones, H. Nguyen, and T. D. Nguyen. Fair k-centers via maximum matching. In _ICML_ , pp. 4940–4949, 2020.
  * [20] M. Kleindessner, P. Awasthi, and J. Morgenstern. Fair k-center clustering for data summarization. In _ICML_ , pp. 3448–3457, 2019.
  * [21] M. Kunaver and T. Pozrl. Diversity in recommender systems - A survey. _Knowl.-Based Syst._ , 123 (2017), pp. 154–162.
  * [22] Z. Liu, P. Luo, X. Wang, and X. Tang. Deep learning face attributes in the wild. In _ICCV_ , pp. 3730–3738, 2015.
  * [23] Z. Moumoulidou, A. McGregor, and A. Meliou. Diverse data selection under fairness constraints. In _ICDT_ , pp. 13:1–13:25, 2021.
  * [24] H. Narasimhan, A. Cotter, M. R. Gupta, and S. Wang. Pairwise fairness for ranking and regression. In _AAAI_ , pp. 5248–5255, 2020.
  * [25] A. Olteanu, C. Castillo, F. Diaz, and E. Kiciman. Social data: Biases, methodological pitfalls, and ethical boundaries. _Front. Big Data_ , 2:13 (2019).
  * [26] S. S. Ravi, D. J. Rosenkrantz, and G. K. Tayi. Heuristic and special case algorithms for dispersion problems. _Oper. Res._ , 42:2 (1994), pp. 299–310.
  * [27] N. Reimers and I. Gurevych. Sentence-BERT: Sentence embeddings using siamese BERT-networks. In _EMNLP/IJCNLP_ , pp. 3980–3990, 2019.
  * [28] G. S. Sankar, A. Louis, M. Nasre, and P. Nimbhorkar. Matchings with group fairness constraints: Online and offline algorithms. In _IJCAI_ , pp. 377–383, 2021.
  * [29] Y. Wang, F. Fabbri, and M. Mathioudakis. Fair and representative subset selection from data streams. In _WWW_ , pp. 1340–1350, 2021.
  * [30] Y. Wang, F. Fabbri, and M. Mathioudakis. Streaming algorithms for diversity maximization with fairness constraints. In _ICDE_ , pp. 41–53, 2022.
  * [31] S. A. Zadeh, M. Ghadiri, V. S. Mirrokni, and M. Zadimoghaddam. Scalable feature selection via distributed diversity maximization. In _AAAI_ , pp. 2876–2883, 2017.
  * [32] M. Zehlike, F. Bonchi, C. Castillo, S. Hajian, M. Megahed, and R. Baeza-Yates. Fa*ir: A fair top-k ranking algorithm. In _CIKM_ , pp. 1569–1578, 2017.
  * [33] R. S. Zemel, Y. Wu, K. Swersky, T. Pitassi, and C. Dwork. Learning fair representations. In _ICML_ , pp. 325–333, 2013.
  * [34] M. Zhang, H. Li, S. Pan, X. Chang, and S. W. Su. Overcoming multi-model forgetting in one-shot NAS with diversity maximization. In _CVPR_ , pp. 7806–7815, 2020.

##  A Data Preparation

Detailed information about the four real-world datasets we use and the
preprocessing procedures for them are presented as follows.

  * •

Adult is retrieved from the UCI Machine Learning
Repository333archive.ics.uci.edu/ml/datasets/adult. It is a collection of
48,842 records from the 1994 US Census database. We select six numeric
attributes as features and normalize each to have zero mean and unit standard
deviation. The $l_{2}$-distance (Euclidean distance) is used as the distance
metric. The groups are generated from two demographic attributes: _sex_ and
_race_. By using them individually and in combination, there are 2 (sex), 5
(race), and 10 (sex + race) groups, respectively.

  * •

CelebA is provided by Liu _et al._ [22] on the
website444mmlab.ie.cuhk.edu.hk/projects/CelebA.html. It is a set of 202,599
images of human faces. We get a 25,088-dimensional ($512\times 7\times 7$)
feature vector for each image from the pre-trained VGG16 model in
Keras555https://keras.io/api/applications/vgg/. The $l_{1}$-distance
(Manhattan distance) between feature vectors is used as the distance metric.
We generate 2 groups from a human-annotated class label “ _sex_ ” {‘female’,
‘male’}, 2 groups from another human-annotated class label “ _age_ ” {‘young’,
‘not young’}, and 4 groups from both of them, respectively.

  * •

Census is also retrieved from the UCI Machine Learning
Repository666archive.ics.uci.edu/ml/datasets/US+Census+Data+(1990). It is a
set of 2,426,116 records from the 1990 US Census data. We take 25 (normalized)
numeric attributes as features and use the $l_{1}$-distance (Manhattan
distance) as the distance metric. We generate 2, 7, and 14 groups from two
demographic attributes _sex_ , _age_ , and both of them, respectively.

  * •

Twitter is retrieved from Kaggle777www.kaggle.com/crowdflower/twitter-user-
gender-classification. It is a collection of 18,836 tweets with user profiles.
We transform each tweet into a 1,024-dimensional feature vector using the
sentence-transformer model888huggingface.co/models?library=sentence-
transformers [27] (“bert-large-nli-stsb-mean-tokens”). The angular distance is
used as the distance metric. We generate 3 groups from the attribute “ _sex_ ”
{‘female’, ‘male’, ‘non-human’} in user profiles.

The proportion of each group on each dataset is provided in Table 4.

Table 4: Proportion of each group on each dataset. Dataset | Group | Proportion of Each Group
---|---|---
Adult | Sex | ‘Female’: 33.2%, ‘Male’: 66.8%
Race |  | ‘Amer-Indian-Eskimo’: 1.0%, ‘Asian-Pac-Islander’: 3.1%, ‘Black’: 9.6%,
---
‘Others’: 0.8%, ‘White’: 85.5%
Sex+Race |  | ‘AIE+F’: 0.4%, ‘API+F’: 1.1%, ‘B+F’: 4.7%, ‘O+F’: 0.3%, ‘W+F’: 26.7%,
---
‘AIE+M’: 0.6%, ‘API+M’: 2.0%, ‘B+M’: 4.9%, ‘O+M’: 0.5%, ‘W+M’: 58.8%
CelebA | Sex | ‘Female’: 58.3%, ‘Male’: 41.7%
Age | ‘Not Young’: 22.6%, ‘Young’: 77.4%
Sex+Age | ‘NY+F’: 7.3%, ‘Y+F’: 51.0%, ‘NY+M’: 15.3%, ‘Y+M’: 26.4%
Census | Sex | ‘Female’ : 51.6%, ‘Male’ : 48.4%
Age |  | ‘A1 (12-)’: 18.2%, ‘A2 (13-19)’: 10.0%, ‘A3 (20-29)’: 15.3%,
---
‘A4 (30-39)’: 16.7%, ‘A5 (40-49)’: 12.9%, ‘A6 (50-64)’: 13.6%,
‘A7 (65+)’: 13.3%
Sex+Age |  | ‘A1+F’: 8.9%, ‘A2+F’: 4.9%, ‘A3+F’: 7.7%, ‘A4+F’: 8.5%, ‘A5+F’: 6.6%,
---
‘A6+F’: 7.2%, ‘A7+F’: 7.9%, ‘A1+M’: 9.3%, ‘A2+M’: 5.1%, ‘A3+M’: 7.6%,
‘A4+M’: 8.2%, ‘A5+M’: 6.3%, ‘A6+M’: 6.5%, ‘A7+M’: 5.4%
Twitter | Sex | ‘Female’: 35.6%, ‘Male’: 32.9%, ‘Non-Human’: 31.5%

(a) Adult (Sex)

(b) Adult (Race)

(c) Adult (S+R)

(d) CelebA (Sex)

(e) CelebA (Age)

(f) CelebA (S+A)

(g) Census (Sex)

(h) Census (Age)

(i) Twitter (Sex)

Figure 8: Results of FMMD-S with varying the parameter $\varepsilon$ for
solution size $k=10$. The error bars in each plot indicate the maximum and
minimum of the diversity value and running time over $10$ runs, respectively.
In all plots for diversity values, the blue horizontal lines denote the
diversity values of the optimal solutions provided by FMMD-E, which measure
the gaps between the approximate solutions of FMMD-S and the optimal ones.

##  B Parameter Tuning for FMMD-S

Figure 8 illustrates the performance of FMMD-S by varying the parameter
$\varepsilon$ from $0.001$ to $0.5$ for solution size $k=10$ on small datasets
($n=1,000$). Regarding solution quality, the diversity values of the solutions
of FMMD-S remain approximately constant when $\varepsilon$ takes small values.
However, they decrease and become less stable as $\varepsilon$ becomes larger.
Especially, when $\varepsilon=0.5$, FMMD-S cannot provide stable and high-
quality solutions in most cases. In terms of efficiency, the running time
increases significantly and becomes less stable for smaller $\varepsilon$,
particularly when $\varepsilon\leq 0.01$. These results conform to our
theoretical analyses of FMMD-S. The above results show that the most
appropriate value of $\varepsilon$ lies in the range $[0.01,0.1]$ in most
cases. Therefore, we decide to set $\varepsilon=0.05$ in all other experiments
throughout this paper.