# Fairness in Streaming Submodular Maximization over a Matroid Constraint

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 55 references that are in the map.
- First posted on arXiv 24 May 2023.

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

- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Fairness in Learning: Classic and Contextual Bandits](https://mlsanity.com/paper/1605.07139/) (2016)
- [Ranking with Fairness Constraints](https://mlsanity.com/paper/1704.06840/) (2017)
- [Scalable Fair Clustering](https://mlsanity.com/paper/1902.03519/) (2019)
- [Policy Learning for Fairness in Ranking](https://mlsanity.com/paper/1902.04056/) (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)
- [Group-Fairness in Influence Maximization](https://mlsanity.com/paper/1903.00967/) (2019)
- [Exploring Algorithmic Fairness in Robust Graph Covering Problems](https://mlsanity.com/paper/2006.06865/) (2020)
- [Submodular Maximization Meets Streaming: Matchings, Matroids, and More](https://mlsanity.com/paper/1309.2038/) (2013)
- [Streaming Robust Submodular Maximization: A Partitioned Thresholding Approach](https://mlsanity.com/paper/1711.02598/) (2017)
- [Do Less, Get More: Streaming Submodular Maximization with Subsampling](https://mlsanity.com/paper/1802.07098/) (2018)
- [Fair Influence Maximization: A Welfare Optimization Approach](https://mlsanity.com/paper/2006.07906/) (2020)
- [A Unified Approach to Fair Online Learning via Blackwell Approachability](https://mlsanity.com/paper/2106.12242/) (2021)
- [Beyond 1/2-Approximation for Submodular Maximization on Massive Data Streams](https://mlsanity.com/paper/1808.01842/) (2018)
- [A Technique for Obtaining True Approximations for k-Center with Covering Constraints](https://mlsanity.com/paper/2007.03946/) (2020)
- [Fair Colorful k-Center Clustering](https://mlsanity.com/paper/2007.04059/) (2020)
- [Streaming Submodular Maximization under Matroid Constraints](https://mlsanity.com/paper/2107.07183/) (2021)
- [The One-way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness](https://mlsanity.com/paper/2003.13459/) (2020)
- [Multiwinner Approval Rules as Apportionment Methods](https://mlsanity.com/paper/1611.08691/) (2016)
- [Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model](https://mlsanity.com/paper/2002.05477/) (2020)
- [Semi-Streaming Algorithms for Submodular Matroid Intersection](https://mlsanity.com/paper/2102.04348/) (2021)
- [Space Lower Bounds for Approximating Maximum Matching in the Edge Arrival Model](https://mlsanity.com/paper/2103.11669/) (2021)

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

- [Fairness in Submodular Maximization over a Matroid Constraint](https://mlsanity.com/paper/2312.14299/) (2023)
- [Consistent Submodular Maximization](https://mlsanity.com/paper/2405.19977/) (2024)
- [Bridging the Gap Between General and Down-Closed Convex Sets in Submodular Maximization](https://mlsanity.com/paper/2401.09251/) (2024)

## Abstract (arXiv)

Streaming submodular maximization is a natural model for the task of selecting a representative subset from a large-scale dataset. If datapoints have sensitive attributes such as gender or race, it becomes important to enforce fairness to avoid bias and discrimination. This has spurred significant interest in developing fair machine learning algorithms. Recently, such algorithms have been developed for monotone submodular maximization under a cardinality constraint. In this paper, we study the natural generalization of this problem to a matroid constraint. We give streaming algorithms as well as impossibility results that provide trade-offs between efficiency, quality and fairness. We validate our findings empirically on a range of well-known real-world applications: exemplar-based clustering, movie recommendation, and maximum coverage in social networks.