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. We note that ratio \alpha  -\epsilon can be achieved using  {(1/\epsilon)}^{O(1/\epsilon^4)}n\log n value oracle calls, but this algorithm is impractical already for large } values of \epsilon. Among practical algorithms  , our is the currently best known one .
We consider the problem of maximizing a non-negative monotone 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 appropriate elements of an optimal solution , and then executing a greedy algorithm, one can obtain the optimal approximation ratio of \alpha = 1-1/e \approx 0.632 for BSM. However, the need to guess (by enumeration) 3 elements makes the algorithm of Sviridenko impractical as it leads to a time complexity of O(n^5) (which can be slightly improved using the thresholding technique of Badanidiyuru 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 , we get an almost as good approximation ratio of 0.6174>0.9767\alpha in roughly O(n^2) time. Prior to our work, the only algorithms that were known to obtain an approximation ratio close to \alpha for BSM were the algorithm of Sviridenko and an algorithm of Ene Nguyen (2019) that achieves (\alpha -\epsilon )-approximation. However, the algorithm of Ene Nguyen requires {(1/\epsilon)}^{O(1/\epsilon^4)}n\log ^2 n time, and hence, is of theoretical interest only as (1/\epsilon)}^{O(1/\epsilon^4) values of \epsilon. In contrast, all the algorithms we analyze are simple and parallelizable, which makes them good candidates for practical use. Recently, Tang et al. (2020) studied a simple greedy algorithm that already has a long research history, and proved that its approximation ratio is at least 0.405. We improve over this result, and show that the approximation ratio of this algorithm is within the range 0.427 , 0.462 .
R
Budgeted Submodular Maximization problem , that seeks to maximize an increasing
problem of maximizing a non-negative monotone
R
budget constraints. Extending a result of Khuller, Moss, and Naor for the Budgeted Coverage problem, Sviridenko showed that the greedy algorithm combined with
a knapsack constraint, which is also known as the Budgeted Submodular Maximization (BSM) problem. Sviridenko (2004) showed that by
R
most profitable
appropriate
R
has approximation ratio
, and then executing a greedy algorithm, one can obtain the optimal approximation ratio of
R
1-\frac{1
1-1/e
R
. We show that just 2 guesses sufficeto achieve ratio \alpha
for BSM. However, the need to guess (by enumeration) 3 elements makes the algorithm of Sviridenko impractical as it leads to a time complexity of O(n^5) (which can be slightly improved using the thresholding technique of Badanidiyuru
A
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
R
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. We note that ratio \alpha
we get an almost as good approximation ratio of 0.6174>0.9767\alpha in roughly O(n^2) time. Prior to our work, the only algorithms that were known to obtain an approximation ratio close to \alpha for BSM were the algorithm of Sviridenko and an algorithm of Ene
A
Nguyen (2019) that achieves (\alpha
R
can be achieved using
)-approximation. However, the algorithm of Ene
A
Nguyen requires
R
n value oracle calls, but this algorithm is impractical already for large
^2 n time, and hence, is of theoretical interest only as
A
(1/\epsilon)
A
^{O(1/\epsilon^4)
R
Among practical algorithms
In contrast, all the algorithms we analyze are simple and parallelizable, which makes them good candidates for practical use. Recently, Tang et al. (2020) studied a simple greedy algorithm that already has a long research history, and proved that its approximation ratio is at least 0.405. We improve over this result, and show that the approximation ratio of this algorithm is within the range
A
0.427
R
our is the currently best known one
0.462