4 papers
Submodular Welfare Maximization with Budget Constraints in the Random-Order Model
Max Klimm, Martin Knaack
We study an online item-allocation problem with budgets and a submodular objective. A set of agents is known in advance, and each agent has a known budget. A set of ite…
Generalized Assignment and Knapsack Problems in the Random-Order Model
Max Klimm, Martin Knaack
We study different online optimization problems in the random-order model. There is a finite set of bins with known capacity and a finite set of items arriving in a random order. U…
Maximizing a Submodular Function with Bounded Curvature under an Unknown Knapsack Constraint
Max Klimm, Martin Knaack
This paper studies the problem of maximizing a monotone submodular function under an unknown knapsack constraint. A solution to this problem is a policy that decides which item to…
Packing a Knapsack with Items Owned by Strategic Agents
Javier Cembrano, Max Klimm, Martin Knaack
This paper considers a scenario within the field of mechanism design without money where a mechanism designer is interested in selecting items with maximum total value under a knap…