Ehud Altman, Kenneth R. Brown, et al.
PRX Quantum
Paper
A note on maximizing a submodular set function subject to a knapsack constraint
Abstract
A note on maximizing a submodular set function subject to a knapsack constraint was presented. An (1-e-1)-approximation algorithm for maximizing a nondecreasing submodular set function was obtained. This algorithm required O(n5) function value computations. The algorithm enumerated all feasible solutions of cardinality one or two.
Related
Ziv Bar-Yossef, T.S. Jayram, et al.
Journal of Computer and System Sciences
George Markowsky
J. Math. Anal. Appl.
W.C. Tang, H. Rosen, et al.
SPIE Optics, Electro-Optics, and Laser Applications in Science and Engineering 1991