Sabine Münch We consider the problem of maximizing a monotone increasing, normalized, and submodular function defined on a set of weighted items under a knapsack constraint. A well-known greedy algorithm, analyzed by Wolsey (1982), achieves an approximation factor of \(0.357\) for this problem. This greedy algorithm starts with an empty solution set and iteratively generates a feasible … Read more
We consider a game-theoretic variant of maximizing a monotone increasing, submodular function under a cardinality constraint. Initially, a solution to this classical problem is determined. Subsequently, a predetermined number of elements from the ground set, not necessarily contained in the initial solution, are deleted, potentially reducing the solution’s cardinality. If any deleted elements were part … Read more
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 … Read more