3 papers
cs.DS2026
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…
cs.DS2025
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…
cs.GT2024
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…