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

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 35 references that are in the map.
- First posted on arXiv 5 Jan 2023.

## Builds on (most cited first, 15 of 15)

- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [Deep Learning Face Attributes in the Wild](https://mlsanity.com/paper/1411.7766/) (2014)
- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [FA*IR: A Fair Top-k Ranking Algorithm](https://mlsanity.com/paper/1706.06368/) (2017)
- [Ranking with Fairness Constraints](https://mlsanity.com/paper/1704.06840/) (2017)
- [Fair k-Center Clustering for Data Summarization](https://mlsanity.com/paper/1901.08628/) (2019)
- [Pairwise Fairness for Ranking and Regression](https://mlsanity.com/paper/1906.05330/) (2019)
- [Fair and Diverse DPP-based Data Summarization](https://mlsanity.com/paper/1802.04023/) (2018)
- [Fairness in Streaming Submodular Maximization: Algorithms and Hardness](https://mlsanity.com/paper/2010.07431/) (2020)
- [How to Solve Fair k-Center in Massive Data Models](https://mlsanity.com/paper/2002.07682/) (2020)
- [Matchings with Group Fairness Constraints: Online and Offline Algorithms](https://mlsanity.com/paper/2105.09522/) (2021)
- [Diverse Data Selection under Fairness Constraints](https://mlsanity.com/paper/2010.09141/) (2020)
- [MapReduce and Streaming Algorithms for Diversity Maximization in Metric Spaces of Bounded Doubling Dimension](https://mlsanity.com/paper/1605.05590/) (2016)
- [Improved Approximation and Scalability for Fair Max-Min Diversification](https://mlsanity.com/paper/2201.06678/) (2022)
- [Streaming Algorithms for Diversity Maximization with Fairness Constraints](https://mlsanity.com/paper/2208.00194/) (2022)

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

- [Fast and Robust: Task Sampling with Posterior and Diversity Synergies for Adaptive Decision-Makers in Randomized Environments](https://mlsanity.com/paper/2504.19139/) (2025)
- [GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility](https://mlsanity.com/paper/2405.18754/) (2024)

## Abstract (arXiv)

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 frac1-varepsilon5-approximation algorithm for any varepsilon ∈ (0, 1) that scales to large datasets. Extensive experiments on real-world datasets demonstrate the superior performance of our proposed algorithms over existing ones.