Guillaume Buthmann, Tomoya Sakai, et al.
ICASSP 2025
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
Satoshi Hada
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Vladimir Yanovski, Israel A. Wagner, et al.
Ann. Math. Artif. Intell.
Arnon Amir, Michael Lindenbaum
IEEE Transactions on Pattern Analysis and Machine Intelligence