article Open access

Practical Budgeted Submodular Maximization

Moran Feldman^a✉, Zeev Nutov^{b c}, Elad Shoham^{b c}

^aUniversity of Haifa, Haifa, Israel
^bThe Open University of Israel, Ra’anana, Israel
^cThe Open University of Israel, Ra'anana, Israel
✉Corresponding author

Algorithmica Springer Science+Business Media2022-12-10 28 citations28 references

Looking for the full paper…

Export

Papers open inside SciRah from the original publisher or repository; SciRah never hosts them.

Abstract

No abstract is available from our sources. Use “Read paper” to view it.

TL;DRThis paper considers the problem of maximizing a non-negative monotone submodular function subject to a knapsack constraint, and shows that fewer guesses suffice, and gets the same optimal approximation ratio of α with an improved time complexity. (Semantic Scholar)

Plain-language summary

AI illustration of the topic of “Practical Budgeted Submodular Maximization”

Practical Budgeted Submodular Maximization

Abstract

Plain-language summary

Discussion