Fair Submodular Cover

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.