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 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 Vondrak (2014), but only to roughly O(n^4)). Our main results in this paper show that fewer guesses suffice. Specifically, by making only 2 guesses, we get the same optimal approximation ratio of \alpha with an improved time complexity of roughly O(n^3). Furthermore, by making only a single guess , 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.