Consider the problem of maximizing a nondecreasing submodular function defined on a set of weighted items under an unknown knapsack capacity.
Assume items are packed sequentially into the knapsack and the knapsack capacity is accessed through an oracle that answers whether an item fits into the currently packed knapsack. If an item is tried to be added and fits, it is packed irrevocably; if the addition exceeds the knapsack capacity, it is removed from consideration. We consider nonadaptive packing according to a predetermined sequence, denoted universal policy. We present an algorithm to compute universal policies that perform for any unknown but fixed capacity (which is assumed to be greater or equal to the heaviest item), at least as good as the classic algorithm due to Wolsey, which packs the knapsack according to steepest ascent and outputs the better of the currently packed knapsack and the first item that exceeds the knapsack capacity, applied to the same capacity.
As a byproduct, we obtain an adaptive algorithm for the problem of maximizing a monotone-increasing submodular function and a universal policy for maximizing a modular function, respectively, under an unknown knapsack capacity. Our algorithms perform at least as well as the best known algorithms for the respective problem, but are far more intuitive and allow for simpler proofs of correctness than the ones provided in literature. Furthermore, submodular instances exist where our adaptive algorithm performs strictly better than the best known adaptive algorithm from the literature.
Article
View Maximizing a Monotone Submodular Function Under an Unknown Knapsack Capacity