  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 $f_1,...,f_m$; $m$ thresholds $T_1,...,T_m$ and a
non-negative integer $r$, MinRF asks for the smallest set $S$ such that for all
$i \in [m]$, $\min_{|X| \leq r} f_i(S \setminus X) \geq T_i$. We prove that
MinRF is inapproximable within $(1-\epsilon)\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.
