  Consider the following variant of the set cover problem. We are given a
universe $U=\{1,...,n\}$ and a collection of subsets $\mathcal{C} =
\{S_1,...,S_m\}$ where $S_i \subseteq U$. For every element $u \in U$ we need
to find a set $\phi(u) \in \mathcal C$ such that $u\in \phi(u)$. Once we
construct and fix the mapping $\phi:U \rightarrow \mathcal{C}$ a subset $X
\subseteq U$ of the universe is revealed, and we need to cover all elements
from $X$ with exactly $\phi(X):=\cup_{u\in X} \phi(u)$. The goal is to find a
mapping such that the cover $\phi(X)$ is as cheap as possible.
  This is an example of a universal problem where the solution has to be
created before the actual instance to deal with is revealed. Such problems
appear naturally in some settings when we need to optimize under uncertainty
and it may be actually too expensive to begin finding a good solution once the
input starts being revealed.
  A rich body of work was devoted to investigate the approximability of such
problems under the regime of worst case analysis or when the input instance is
drawn randomly from some probability distribution. Here one typically compares
the quality of the produced solution with the optimal offline solution.
  In this paper we consider a different viewpoint: What if we would compare our
approximate universal solution against an optimal universal solution that obeys
the same rules as we do? We show that under this viewpoint it is possible to
achieve improved approximation algorithms for the stochastic version of
universal set cover. Our result is based on rounding a proper configuration IP
that captures the optimal universal solution, and using tools from submodular
optimization. The same basic approach leads to improved approximation
algorithms also for other related problems.
