Michael E. Henderson
International Journal of Bifurcation and Chaos in Applied Sciences and Engineering
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
Simeon Furrer, Dirk Dahlhaus
ISIT 2005
Juliann Opitz, Robert D. Allen, et al.
Microlithography 1998
Vladimir Yanovski, Israel A. Wagner, et al.
Ann. Math. Artif. Intell.