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…
Faster Symmetric Rendezvous on Four or More Locations
Javier Cembrano, Felix Fischer, Max Klimm
In the symmetric rendezvous problem, two players follow the same (randomized) strategy to visit one of locations in each time step . Their goal is to minimize th…
Impartial Selection with Predictions
Javier Cembrano, Felix Fischer, Max Klimm
We study the selection of agents based on mutual nominations, a theoretical problem with many applications from committee selection to AI alignment. As agents both select and are s…
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…