  Given an $n$-point metric space $(\mathcal{X},d)$ where each point belongs to
one of $m=O(1)$ different categories or groups and a set of integers $k_1,
\ldots, k_m$, the fair Max-Min diversification problem is to select $k_i$
points belonging to category $i\in [m]$, such that the minimum pairwise
distance between selected points is maximized. The problem was introduced by
Moumoulidou et al. [ICDT 2021] and is motivated by the need to down-sample
large data sets in various applications so that the derived sample achieves a
balance over diversity, i.e., the minimum distance between a pair of selected
points, and fairness, i.e., ensuring enough points of each category are
included. We prove the following results:
  1. We first consider general metric spaces. We present a randomized
polynomial time algorithm that returns a factor $2$-approximation to the
diversity but only satisfies the fairness constraints in expectation. Building
upon this result, we present a $6$-approximation that is guaranteed to satisfy
the fairness constraints up to a factor $1-\epsilon$ for any constant
$\epsilon$. We also present a linear time algorithm returning an $m+1$
approximation with exact fairness. The best previous result was a $3m-1$
approximation.
  2. We then focus on Euclidean metrics. We first show that the problem can be
solved exactly in one dimension. For constant dimensions, categories and any
constant $\epsilon>0$, we present a $1+\epsilon$ approximation algorithm that
runs in $O(nk) + 2^{O(k)}$ time where $k=k_1+\ldots+k_m$. We can improve the
running time to $O(nk)+ poly(k)$ at the expense of only picking $(1-\epsilon)
k_i$ points from category $i\in [m]$.
  Finally, we present algorithms suitable to processing massive data sets
including single-pass data stream algorithms and composable coresets for the
distributed processing.
