6 papers
When to Identify Is to Control: On the Controllability of Combinatorial Optimization Problems
Max Klimm, Jannik Matuschke
Consider a finite ground set , a set of feasible solutions , and a class of objective functions defined on . We are interested in su…
Public Signals in Network Congestion Games
Svenja M. Griesbach, Martin Hoefer, Max Klimm +1
We consider a largely untapped potential for the improvement of traffic networks that is rooted in the inherent uncertainty of travel times. Travel times are subject to stochastic…
Incremental-Decremental Maximization
Yann Disser, Max Klimm, Annette Lutz +1
We introduce a framework for incremental-decremental maximization that captures the gradual transformation or renewal of infrastructures. In our model, an initial solution is trans…
Improved Approximation Algorithms for the Expanding Search Problem
Svenja M. Griesbach, Felix Hommelsheim, Max Klimm +1
A searcher is tasked with exploring a graph with edge lengths and vertex weights, starting from a designated vertex. Initially, only the starting vertex is considered explored. At…
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…
Impartial Selection with Additive Guarantees via Iterated Deletion
Javier Cembrano, Felix Fischer, David Hannon +1
Impartial selection is the selection of an individual from a group based on nominations by other members of the group, in such a way that individuals cannot influence their own cha…