# Fairness in Submodular Maximization over a Matroid Constraint

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 66 references that are in the map.
- First posted on arXiv 21 Dec 2023.

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

- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Ranking with Fairness Constraints](https://mlsanity.com/paper/1704.06840/) (2017)
- [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)
- [Constrained Submodular Maximization via a Non-symmetric Technique](https://mlsanity.com/paper/1611.03253/) (2016)
- [Constrained Submodular Maximization via New Bounds for DR-Submodular Functions](https://mlsanity.com/paper/2311.01129/) (2023)
- [Resolving the Approximability of Offline and Online Non-monotone DR-Submodular Maximization over General Convex Sets](https://mlsanity.com/paper/2210.05965/) (2022)
- [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)
- [Lyapunov function approach for approximation algorithm design and analysis: with applications in submodular maximization](https://mlsanity.com/paper/2205.12442/) (2022)
- [Multiwinner Approval Rules as Apportionment Methods](https://mlsanity.com/paper/1611.08691/) (2016)
- [Computing Welfare-Maximizing Fair Allocations of Indivisible Goods](https://mlsanity.com/paper/2012.03979/) (2020)
- [Multi-Objective Maximization of Monotone Submodular Functions with Cardinality Constraint](https://mlsanity.com/paper/1711.06428/) (2017)
- [Group Fairness in Non-monotone Submodular Maximization](https://mlsanity.com/paper/2302.01546/) (2023)
- [Fairness in Streaming Submodular Maximization over a Matroid Constraint](https://mlsanity.com/paper/2305.15118/) (2023)
- [Semi-Streaming Algorithms for Submodular Matroid Intersection](https://mlsanity.com/paper/2102.04348/) (2021)
- [Balancing Utility and Fairness in Submodular Maximization (Technical Report)](https://mlsanity.com/paper/2211.00980/) (2022)
- [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)

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

- [Fair Submodular Cover](https://mlsanity.com/paper/2407.04804/) (2024)
- [Bridging the Gap Between General and Down-Closed Convex Sets in Submodular Maximization](https://mlsanity.com/paper/2401.09251/) (2024)

## Abstract (arXiv)

Submodular maximization over a matroid constraint is a fundamental problem with various applications in machine learning. Some of these applications involve decision-making over datapoints with sensitive attributes such as gender or race. In such settings, it is crucial to guarantee that the selected solution is fairly distributed with respect to this attribute. Recently, fairness has been investigated in submodular maximization under a cardinality constraint in both the streaming and offline settings, however the more general problem with matroid constraint has only been considered in the streaming setting and only for monotone objectives. This work fills this gap. We propose various algorithms and impossibility results offering different trade-offs between quality, fairness, and generality.