  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 $D$ over elements of $\mathcal{U}$. The algorithm draws
$n$ elements one-by-one from $D$ and must buy a set to cover each element on
arrival; the goal is to minimize the total cost of sets bought during this
process. A universal algorithm a priori maps each element $u \in \mathcal{U}$
to a set $S(u)$ such that if $U \subseteq \mathcal{U}$ is formed by drawing $n$
times from distribution $D$, then the algorithm commits to outputting $S(U)$.
Grandoni et al. gave an $O(\log mN)$-competitive universal algorithm for this
stochastic set cover problem.
  We improve unilaterally upon this result by giving a simple, polynomial time
$O(\log mn)$-competitive universal algorithm for the more general prophet
version, in which $U$ is formed by drawing from $n$ different distributions
$D_1, \ldots, D_n$. Furthermore, we show that we do not need full foreknowledge
of the distributions: in fact, a single sample from each distribution suffices.
We show similar results for the 2-stage prophet setting and for the
online-with-a-sample setting.
  We obtain our results via a generic reduction from the single-sample prophet
setting to the random-order setting; this reduction holds for a broad class of
minimization problems that includes all covering problems. We take advantage of
this framework by giving random-order algorithms for non-metric facility
location and set multicover; using our framework, these automatically translate
to universal prophet algorithms.
