# Improved Approximation and Scalability for Fair Max-Min Diversification

arXiv: https://arxiv.org/abs/2201.06678 · HTML: https://mlsanity.com/paper/2201.06678/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Jan 2022.

## Built on by (most cited first, 3 of 3)

- [Core-sets for Fair and Diverse Data Summarization](https://mlsanity.com/paper/2310.08122/) (2023)
- [Max-Min Diversification with Fairness Constraints: Exact and Approximation Algorithms](https://mlsanity.com/paper/2301.02053/) (2023)
- [GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility](https://mlsanity.com/paper/2405.18754/) (2024)

## Abstract (arXiv)

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.