Efficient Branch-and-Bound for Submodular Function Maximization under Knapsack Constraint

Yimin Hao, Yi Zhou, Chao Xu +1

The submodular knapsack problem (SKP), which seeks to maximize a submodular set function by selecting a subset of elements within a given budget, is an important discrete optimizat…