Set Covering with Our Eyes Wide Shut

Anupam Gupta, Gregory Kehne, Roie Levin

In the stochastic set cover problem (Grandoni et al., FOCS '08), we are given a collection $\mathcal{S}$ of $m$ sets over a universe $\mathcal{U}$ of size $N$, and a distribution $…