# Streaming Algorithms for Diversity Maximization with Fairness Constraints

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 42 references that are in the map.
- First posted on arXiv 30 Jul 2022.

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

- [Fair k-Center Clustering for Data Summarization](https://mlsanity.com/paper/1901.08628/) (2019)
- [Coresets for Clustering with Fairness Constraints](https://mlsanity.com/paper/1906.08484/) (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)
- [Matroid and Knapsack Center Problems](https://mlsanity.com/paper/1301.0745/) (2013)
- [Diverse Data Selection under Fairness Constraints](https://mlsanity.com/paper/2010.09141/) (2020)
- [Faster Matroid Intersection](https://mlsanity.com/paper/1911.10765/) (2019)
- [MapReduce and Streaming Algorithms for Diversity Maximization in Metric Spaces of Bounded Doubling Dimension](https://mlsanity.com/paper/1605.05590/) (2016)
- [Local Search for Max-Sum Diversification](https://mlsanity.com/paper/1607.04557/) (2016)
- [Max-sum diversity via convex programming](https://mlsanity.com/paper/1511.07077/) (2015)
- [A note on Cunningham's algorithm for matroid intersection](https://mlsanity.com/paper/1904.04129/) (2019)
- [Maximizing diversity over clustered data](https://mlsanity.com/paper/2001.03050/) (2020)

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

- [Fair Streaming Principal Component Analysis: Statistical and Algorithmic Viewpoint](https://mlsanity.com/paper/2310.18593/) (2023)
- [Max-Min Diversification with Fairness Constraints: Exact and Approximation Algorithms](https://mlsanity.com/paper/2301.02053/) (2023)
- [Dual-Teacher De-biasing Distillation Framework for Multi-domain Fake News Detection](https://mlsanity.com/paper/2312.01006/) (2023)

## Abstract (arXiv)

Diversity maximization is a fundamental problem with wide applications in data summarization, web search, and recommender systems. Given a set X of n elements, it asks to select a subset S of k ll n elements with maximum diversity, as quantified by the dissimilarities among the elements in S. In this paper, we focus on the diversity maximization problem with fairness constraints in the streaming setting. Specifically, we consider the max-min diversity objective, which selects a subset S that maximizes the minimum distance (dissimilarity) between any pair of distinct elements within it. Assuming that the set X is partitioned into m disjoint groups by some sensitive attribute, e.g., sex or race, ensuring fairness requires that the selected subset S contains ki elements from each group i ∈ [1,m]. A streaming algorithm should process X sequentially in one pass and return a subset with maximum diversity while guaranteeing the fairness constraint. Although diversity maximization has been extensively studied, the only known algorithms that can work with the max-min diversity objective and fairness constraints are very inefficient for data streams. Since diversity maximization is NP-hard in general, we propose two approximation algorithms for fair diversity maximization in data streams, the first of which is frac1-varepsilon4-approximate and specific for m=2, where varepsilon ∈ (0,1), and the second of which achieves a frac1-varepsilon3m+2-approximation for an arbitrary m. Experimental results on real-world and synthetic datasets show that both algorithms provide solutions of comparable quality to the state-of-the-art algorithms while running several orders of magnitude faster in the streaming setting.