Practical Budgeted Submodular Maximization

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 (Operat Res Lett 32:41–43, 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 α= 1 - 1 / e≈ 0.632 for BSM. However, the need to guess (by enumeration) 3 elements makes the algorithm of Sviridenko (Operat Res Lett 32:41–43, 2004) impractical as it leads to a time complexity of roughly O(n⁵) (this time complexity can be slightly improved using the thresholding technique of Badanidiyuru & Vondrák (in: SODA, 1497–1514, 2014) but only to roughly O(n⁴)). Our main results in this paper show that fewer guesses suffice. Specifically, by making only 2 guesses (and using the thresholding technique of Badanidiyuru & Vondrák (in: SODA, 1497–1514, 2014), we get the same optimal approximation ratio of α with an improved time complexity of roughly O(n³). Furthermore, by making only a single guess, we get an almost as good approximation ratio of 0.6174 > 0.9767 α in roughly O(n²) time. Prior to our work, the only approximation algorithms that were known to obtain an approximation ratio close to α for BSM were the algorithm of Sviridenko (Operat Res Lett 32:41–43, 2004) and an algorithm of Ene & Nguyen (in: ICALP, 53:1–53:12, 2019) that achieves (α- ε) -approximation. However, the algorithm of Ene & Nguyen (in: ICALP, 53:1–53:12, 2019) requires (1/ε)O(1/ε4)nlog2n time, and hence, is of theoretical interest only since (1/ε)O(1/ε4) is huge even for moderate values of ε. In contrast, all the algorithms we analyze are simple and parallelizable, which makes them good candidates for practical use. Recently, Tang et al. (in: Proc ACM Meas Anal Comput Syst, 5(1): 08:1–08:22, 2021) studied a simple greedy algorithm that already has a long research history, and proved that it admits an approximation ratio of at least 0.405 (without any guesses). The last part of this paper improves over the result of Tang et al. (in: Proc ACM Meas Anal Comput Syst, 5(1): 08:1–08:22, 2021) and shows that the approximation ratio of this algorithm is within the range [0.427, 0.462].