Before revision:  Extending a result of Khuller, Moss, and Naor for the Budgeted Coverage problem, Sviridenko showed that the greedy algorithm combined with guessing 3 most profitable elements of an optimal solution has approximation ratio \alpha = 1-\frac{1 \approx 0.632 . We show that just 2 guesses sufficeto achieve ratio \alpha  , 1 guesssuffices to achieve ratio 0.899 \alpha \approx 0.568, while ratio 0.68\alpha \approx 0.43 can be achieved without any guessing.
After revision:  Extending a result of Khuller, Moss, and Naor for the Budgeted Coverage problem, Sviridenko showed that the greedy algorithm combined with guessing 3 appropriate elements of an optimal solution has approximation ratio \alpha = 1-\frac{1 \approx 0.632 . We show that just 2 guesses sufficeto achieve ratio \alpha , 1 guesssuffices to achieve ratio 0.899 \alpha \approx 0.568, while ratio 0.68\alpha \approx 0.43 can be achieved without any guessing.