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 of an item exceeds the knapsack capacity, there are two possible approaches: in packing without discarding, packing stops directly, while in packing with discarding, the item is removed from consideration, and packing continues.
Our main result considers non-adaptive packing without discarding according to a predetermined sequence, called universal policy, and presents the first algorithm to compute universal policies that perform for any unknown but fixed knapsack capacity (which is assumed to be greater than or equal to the heaviest item), at least as good as the classic greedy algorithm due to Wolsey (1982) applied to the same known capacity.
Besides, we obtain results for packing with discarding. Specifically, we develop 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. Both are much simpler than those presented in previous literature, while providing the same approximation guarantees.