Max-Min Diversification with Fairness Constraints: Exact and Approximation Algorithms
Preprint
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 \emph{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
All Related Versions
This publication has 18 references indexed in Scilit:
- Streaming Algorithms for Diversity Maximization with Fairness Constraints2022
- Overcoming Multi-Model Forgetting in One-Shot NAS With Diversity Maximization2020
- Better Sliding Window Algorithms to Maximize Subadditive and Diversity Objectives2019
- Exact Algorithms for the Max-Min Dispersion Problem2018
- Diversity in recommender systems – A surveyKnowledge-Based Systems, 2017
- Deep Learning Face Attributes in the Wild2015
- Composable core-sets for diversity and coverage maximization2014
- Diverse Set Selection Over Dynamic DataIEEE Transactions on Knowledge and Data Engineering, 2013
- Diversifying search results2009
- Clustering to minimize the maximum intercluster distanceTheoretical Computer Science, 1985