Improved Approximation and Scalability for Fair Max-Min Diversification

Given an n-point metric space (X,d) where each point belongs to one of m=O(1) different categories or groups and a set of integers k1, ldots, km, the fair Max-Min diversification problem is to select ki points belonging to category i∈ [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-ε for any constant ε. 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 ε>0, we present a 1+ε approximation algorithm that runs in O(nk) + 2O(k) time where k=k1+ldots+km. We can improve the running time to O(nk)+ poly(k) at the expense of only picking (1-ε) ki points from category i∈ [m]. Finally, we present algorithms suitable to processing massive data sets including single-pass data stream algorithms and composable coresets for the distributed processing.