Practical Budgeted Submodular Maximization

07/09/2020
by   Zeev Nutov, et al.
0

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 α=1-1/e≈ 0.632. We show that just 2 guesses suffice to achieve ratio α, 1 guess suffices to achieve ratio 0.899 α≈ 0.568, while ratio 0.68α≈ 0.43 can be achieved without any guessing. We note that ratio α-ϵ can be achieved using (1/ϵ)^O(1/ϵ^4)nlog n value oracle calls, but this algorithm is impractical already for large values of ϵ. Among practical algorithms, our is the currently best known one.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset