Hi everybody,

I stumbled upon the following variant of a Set-Covering problem:

Given are the usual universe $\mathcal{U} = \{ u_1 , \ldots , u_n \}$ of elements, and a family of subsets $\mathcal{S} =\{S_1,\ldots,S_m\}$ with costs $c(S_i)$.

There are sets $S_i = \{u_i\} \in \mathcal{S}, i=1,\ldots,n$ and we know all of their costs $c(S_i)$. These can be seen as "base prices" for the single elements. Furthermore we also know the prices for all sets in $\mathcal{S}' \subset \mathcal{S}$, but we do not know the rest of $\mathcal{S}$.

The question now is: Can we estimate probability for the sets in $\mathcal{S}'$ to be in the optimal cover $C \subseteq \mathcal{S}$?

Are you aware of any literature on this? I searched quite some time already, but all I could find are randomized algorithms for the original weighted set-covering problem, or papers on the probabilistic SCP, which both does not seem to help.

So, any hints / keywords / sources would be greatly appreciated!

Thanks in advance,

Hendrik.