Fair Submodular Cover
<|reference_start|>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:2^U\to\mathbb{R}_{\ge 0}$, a threshold $\tau$, the goal is to find a balanced subset of $S$ with minimum cardinality such that $f(S)\ge\tau$. We first introduce discrete algorithms for FSC that achieve a bicriteria approximation ratio of $(\frac{1}{\epsilon}, 1-O(\epsilon))$. We then present a continuous algorithm that achieves a $(\ln\frac{1}{\epsilon}, 1-O(\epsilon))$-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.<|reference_end|>
@article{chen2024fair,
    title={Fair Submodular Cover},
    author={Wenjing Chen, Shuo Xing, Samson Zhou, Victoria G. Crawford},
    journal={arXiv preprint arXiv:2407.04804},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.04804},
    primaryClass={cs.LG cs.CY cs.DS}
}