Consider the problem of maximizing a monotone-increasing submodular function defined on a set of weighted items under an unknown knapsack capacity.
Assume that items are packed sequentially into the knapsack and that the capacity of the knapsack 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 capacity of the knapsack, it is removed from consideration.
We focus on non-adaptive packing according to a predetermined sequence, called universal policy, and present the first algorithm to compute universal policies that perform for any unknown but fixed knapsack 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 maximizing a monotone-increasing submodular function, and a universal policy for maximizing a modular function under an unknown arbitrary knapsack capacity that are much simpler than those presented in previous literature while providing the same approximation guarantees.
Article
View Maximizing a Monotone Submodular Function Under an Unknown Knapsack Capacity