Simultaneous Individual, Group and Multigroup Fairness in Set Covering Problems

Covering problems are fundamental combinatorial optimization problems with broad connections to clustering, facility location, and various applications such as machine learning and controlling disease outbreaks. In this work we study a variant of the set cover problem that generalizes the partition set cover problem~\citep{bera2014approximation}. In partition set cover, given an instance $(P, S)$ with a universe $P = \cup_{c \in [\ell]} P_c$ (where $[\ell]$ denotes $\{1, 2, \ldots, \ell\}$), a collection of subsets \(S\) (each with associated costs), and coverage requirements $k_1,k_2,\dots,k_\ell$, the objective is to find a subcollection with minimum cost that covers at least $k_c$ elements from each group $c \in [\ell]$. We generalize this problem by allowing for the groups $P = \cup_{c \in [\ell]} P_c$ to be overlapping thus capturing both \emph{group fairness} and \emph{multigroup fairness}. We further allow for probabilistic coverage requirements for each element in the ground set thus capturing the notion of \emph{individual fairness}. Our main result is a randomized iterated-rounding-based algorithm with provable guarantees. Our main result is a randomized iterated rounding based algorithm with provable guarantees. We supplement our theoretical results by showing that algorithm has significantly running times and outperforms the best known algorithm of \citep{inamdar18PartitionSetCover}.