Maximizing a Monotone Submodular Function Under an Unknown Knapsack Capacity
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 … Read more