Before revision: We consider the Budgeted Submodular Maximization problem , that seeks to maximize an increasing submodular function subject to budget constraints. 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: We consider the Budgeted Submodular Maximization problem , that seeks to maximize an increasing submodular function subject to a knapsack constraint, which is also known as the Budgeted Submodular Maximization (BSM) problem. Sviridenko (2004) showed that by 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.