A note on maximizing a submodular set function subject to a knapsack constraint
A note on maximizing a submodular set function subject to a knapsack constraint
M. Sviridenko
2004 · DOI: 10.1016/S0167-6377(03)00062-2
Operations Research Letters · 709 Citations
TLDR
An (1-e^-^1)-approximation algorithm for maximizing a nondecreasing submodular set function subject to a knapsack constraint is obtained and requires O(n^5) function value computations.