# Minimum Robust Multi-Submodular Cover for Fairness

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

## Key facts

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

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

- [Balancing Utility and Fairness in Submodular Maximization (Technical Report)](https://mlsanity.com/paper/2211.00980/) (2022)

## Abstract (arXiv)

In this paper, we study a novel problem, Minimum Robust Multi-Submodular Cover for Fairness (MinRF), as follows: given a ground set V; m monotone submodular functions f1,...,fm; m thresholds T1,...,Tm and a non-negative integer r, MinRF asks for the smallest set S such that for all i ∈ [m], min|X| ≤ r fi(S setminus X) ≥ Ti. We prove that MinRF is inapproximable within (1-ε)ln m; and no algorithm, taking fewer than exponential number of queries in term of r, is able to output a feasible set to MinRF with high certainty. Three bicriteria approximation algorithms with performance guarantees are proposed: one for r=0, one for r=1, and one for general r. We further investigate our algorithms' performance in two applications of MinRF, Information Propagation for Multiple Groups and Movie Recommendation for Multiple Users. Our algorithms have shown to outperform baseline heuristics in both solution quality and the number of queries in most cases.