# Fairness in Streaming Submodular Maximization: Algorithms and Hardness

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Oct 2020.

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

- [A Sociotechnical View of Algorithmic Fairness](https://mlsanity.com/paper/2110.09253/) (2021)
- [Approximation Algorithms for Fair Range Clustering](https://mlsanity.com/paper/2306.06778/) (2023)
- [View-based Explanations for Graph Neural Networks](https://mlsanity.com/paper/2401.02086/) (2024)
- [Deletion Robust Submodular Maximization over Matroids](https://mlsanity.com/paper/2201.13128/) (2022)
- [Fully Dynamic Submodular Maximization over Matroids](https://mlsanity.com/paper/2305.19918/) (2023)
- [Fair Submodular Cover](https://mlsanity.com/paper/2407.04804/) (2024)
- [Group Equality in Adaptive Submodular Maximization](https://mlsanity.com/paper/2207.03364/) (2022)
- [Fair Streaming Principal Component Analysis: Statistical and Algorithmic Viewpoint](https://mlsanity.com/paper/2310.18593/) (2023)
- [Fast Feature Selection with Fairness Constraints](https://mlsanity.com/paper/2202.13718/) (2022)
- [Group Fairness in Non-monotone Submodular Maximization](https://mlsanity.com/paper/2302.01546/) (2023)
- [Streaming Algorithms for Diversity Maximization with Fairness Constraints](https://mlsanity.com/paper/2208.00194/) (2022)
- [Fairness in Streaming Submodular Maximization over a Matroid Constraint](https://mlsanity.com/paper/2305.15118/) (2023)
- [Unmasking Gender Bias in Recommendation Systems and Enhancing Category-Aware Fairness](https://mlsanity.com/paper/2502.17921/) (2025)
- [Balancing Utility and Fairness in Submodular Maximization (Technical Report)](https://mlsanity.com/paper/2211.00980/) (2022)
- [Max-Min Diversification with Fairness Constraints: Exact and Approximation Algorithms](https://mlsanity.com/paper/2301.02053/) (2023)
- [Achieving Long-term Fairness in Submodular Maximization through Randomization](https://mlsanity.com/paper/2304.04700/) (2023)
- [Beyond Submodularity: A Unified Framework of Randomized Set Selection with Group Fairness Constraints](https://mlsanity.com/paper/2304.06596/) (2023)
- [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)
- [A Note on Bias to Complete](https://mlsanity.com/paper/2402.11710/) (2024)
- [Assessment of cognitive characteristics in intelligent systems and predictive ability](https://mlsanity.com/paper/2209.11761/) (2022)
- [Fairness in Monotone k-submodular Maximization: Algorithms and Applications](https://mlsanity.com/paper/2411.05318/) (2024)
- [Model-Free Counterfactual Subset Selection at Scale](https://mlsanity.com/paper/2502.08326/) (2025)

## Abstract (arXiv)

Submodular maximization has become established as the method of choice for the task of selecting representative and diverse summaries of data. However, if datapoints have sensitive attributes such as gender or age, such machine learning algorithms, left unchecked, are known to exhibit bias: under- or over-representation of particular groups. This has made the design of fair machine learning algorithms increasingly important. In this work we address the question: Is it possible to create fair summaries for massive datasets? To this end, we develop the first streaming approximation algorithms for submodular maximization under fairness constraints, for both monotone and non-monotone functions. We validate our findings empirically on exemplar-based clustering, movie recommendation, DPP-based summarization, and maximum coverage in social networks, showing that fairness constraints do not significantly impact utility.