# Fair Submodular Cover

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 49 references that are in the map.
- First posted on arXiv 5 Jul 2024.

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

- [Fair prediction with disparate impact: A study of bias in recidivism prediction instruments](https://mlsanity.com/paper/1610.07524/) (2016)
- [Inherent Trade-Offs in the Fair Determination of Risk Scores](https://mlsanity.com/paper/1609.05807/) (2016)
- [Fairness in Criminal Justice Risk Assessments: The State of the Art](https://mlsanity.com/paper/1703.09207/) (2017)
- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Ranking with Fairness Constraints](https://mlsanity.com/paper/1704.06840/) (2017)
- [Twitch Gamers: a Dataset for Evaluating Proximity Preserving and Structural Role-based Node Embeddings](https://mlsanity.com/paper/2101.03091/) (2021)
- [Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints](https://mlsanity.com/paper/1311.2106/) (2013)
- [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)
- [Robust Submodular Maximization: A Non-Uniform Partitioning Approach](https://mlsanity.com/paper/1706.04918/) (2017)
- ["Bring Your Own Greedy"+Max: Near-Optimal 1/2-Approximations for Submodular Knapsack](https://mlsanity.com/paper/1910.05646/) (2019)
- [Streaming Robust Submodular Maximization: A Partitioned Thresholding Approach](https://mlsanity.com/paper/1711.02598/) (2017)
- [Adversarially Robust Submodular Maximization under Knapsack Constraints](https://mlsanity.com/paper/1905.02367/) (2019)
- [Leveraging Sparsity for Efficient Submodular Data Summarization](https://mlsanity.com/paper/1703.02690/) (2017)
- [Bicriteria Approximation Algorithms for the Submodular Cover Problem](https://mlsanity.com/paper/2309.14558/) (2023)
- [Multiwinner Approval Rules as Apportionment Methods](https://mlsanity.com/paper/1611.08691/) (2016)
- [Fairness in Submodular Maximization over a Matroid Constraint](https://mlsanity.com/paper/2312.14299/) (2023)
- [Near Optimal Algorithms for Hard Submodular Programs with Discounted Cooperative Costs](https://mlsanity.com/paper/1902.10172/) (2019)

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

- [Re-Align: Aligning Vision Language Models via Retrieval-Augmented Direct Preference Optimization](https://mlsanity.com/paper/2502.13146/) (2025)
- [TimePre: Bridging Accuracy, Efficiency, and Stability in Probabilistic Time-Series Forecasting](https://mlsanity.com/paper/2511.18539/) (2025)
- [On Socially Fair Low-Rank Approximation and Column Subset Selection](https://mlsanity.com/paper/2412.06063/) (2024)
- [A Resilience Framework for Bi-Criteria Combinatorial Optimization with Bandit Feedback](https://mlsanity.com/paper/2503.12285/) (2025)
- [NexusFlow: Unifying Disparate Tasks under Partial Supervision via Invertible Flow Networks](https://mlsanity.com/paper/2512.06251/) (2025)
- [Multi-Agent Reinforcement Learning with Submodular Reward](https://mlsanity.com/paper/2603.06810/) (2026)

## Abstract (arXiv)

Submodular optimization is a fundamental problem with many applications in machine learning, often involving decision-making over datasets with sensitive attributes such as gender or age. In such settings, it is often desirable to produce a diverse solution set that is fairly distributed with respect to these attributes. Motivated by this, we initiate the study of Fair Submodular Cover (FSC), where given a ground set U, a monotone submodular function f:2U→ℝ≥ 0, a threshold τ, the goal is to find a balanced subset of S with minimum cardinality such that f(S)≥τ. We first introduce discrete algorithms for FSC that achieve a bicriteria approximation ratio of (frac1ε, 1-O(ε)). We then present a continuous algorithm that achieves a (lnfrac1ε, 1-O(ε))-bicriteria approximation ratio, which matches the best approximation guarantee of submodular cover without a fairness constraint. Finally, we complement our theoretical results with a number of empirical evaluations that demonstrate the effectiveness of our algorithms on instances of maximum coverage.