  We study adaptive greedy algorithms for the problems of stochastic set cover
with perfect and imperfect coverages. In stochastic set cover with perfect
coverage, we are given a set of items and a ground set B. Evaluating an item
reveals its state which is a random subset of B drawn from the state
distribution of the item. Every element in B is assumed to be present in the
state of some item with probability 1. For this problem, we show that the
adaptive greedy algorithm has an approximation ratio of H(|B|), the |B|th
Harmonic number. In stochastic set cover with imperfect coverage, an element in
the ground set need not be present in the state of any item. We show a
reduction from this problem to the former problem; the adaptive greedy
algorithm for the reduced instance has an approxiation ratio of H(|E|), where E
is the set of pairs (F, e) such that the state of item F contains e with
positive probability.
