Max Klimm
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Max Klimm has a total of 86 co-authors. Here are the top co-authors by number of shared publications:
- Yann Disser
TU Darmstadt
17 shared publications - Javier Cembrano
Department of Industrial Engineering, Universidad de Chile, Santiago, Chile
10 shared publications - Tobias Harks
Faculty of Computer Science and Mathematics University of Passau 94032 Passau
8 shared publications - Annette Lutz
TU Darmstadt
7 shared publications - Felix Fischer
School of Mathematical Sciences, Queen Mary University of London, London E1 4NS, United Kingdom
7 shared publications - Marc Emanuel Pfetsch
TU Darmstadt
7 shared publications
Latest Publications
- Open Access
- 7 November 2026
- Published by Springer Nature
- p. 289-304
Incremental–Decremental Optimization for the Transition to Hydrogen
- 7 November 2026
- Published by Springer Nature
- p. 289-304
Open AccessIncremental–Decremental Optimization for the Transition to Hydrogen
- 26 October 2026
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
Public Signals in Affine Network Congestion Games with Uncertain Free-Flow Times
Travel times in road networks are subject to stochastic uncertainty resulting from various parameters. A benevolent mobility service provider observing the actual travel times from data may use its informational advantage to steer the traffic equilibrium in a favorable direction through a processs known as signaling or Bayesian persuasion. Previous work has shown that the underlying signaling problem can be NP-hard to approximate better than [Formula: see text], even for static Wardrop flows with affine cost functions with stochastic offsets. In contrast, we show that in this case, the signaling problem is easy for many networks. First, we tightly characterize the class of single-commodity networks in which full information revelation is always an optimal signaling strategy. Second, we construct a reduction from optimal signaling to computing an optimal collection of active edges for the Wardrop equilibrium. For two states, this allows us to efficiently compute an optimal signaling scheme whenever the number of different active edge sets is bounded by a polynomial in the input size. Using a cell decomposition technique, we extend the approach to a polynomial-time algorithm for multicommodity parallel-edge networks provided that both the number of commodities and states are constant. Funding: This work was supported by Deutsche Forschungsgemeinschaft EXC-2046/1 [Grant 390685689] and Ho 3831/9-1 [Grant 514505843].
- 26 October 2026
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
Public Signals in Affine Network Congestion Games with Uncertain Free-Flow Times
Travel times in road networks are subject to stochastic uncertainty resulting from various parameters. A benevolent mobility service provider observing the actual travel times from data may use its informational advantage to steer the traffic equilibrium in a favorable direction through a processs known as signaling or Bayesian persuasion. Previous work has shown that the underlying signaling problem can be NP-hard to approximate better than [Formula: see text], even for static Wardrop flows with affine cost functions with stochastic offsets. In contrast, we show that in this case, the signaling problem is easy for many networks. First, we tightly characterize the class of single-commodity networks in which full information revelation is always an optimal signaling strategy. Second, we construct a reduction from optimal signaling to computing an optimal collection of active edges for the Wardrop equilibrium. For two states, this allows us to efficiently compute an optimal signaling scheme whenever the number of different active edge sets is bounded by a polynomial in the input size. Using a cell decomposition technique, we extend the approach to a polynomial-time algorithm for multicommodity parallel-edge networks provided that both the number of commodities and states are constant. Funding: This work was supported by Deutsche Forschungsgemeinschaft EXC-2046/1 [Grant 390685689] and Ho 3831/9-1 [Grant 514505843].
- 1 October 2026
- Published by Springer Nature in International Journal of Game Theory
- Vol. 55 (2) , 42
Impartial selection under combinatorial constraints
- 1 October 2026
- Published by Springer Nature in International Journal of Game Theory
- Vol. 55 (2) , 42
Impartial selection under combinatorial constraints
- Open Access
- 14 August 2026
- Published by Springer Nature in Acta Informatica
- Vol. 63 (3) , 31
Incremental–decremental maximization
We introduce a framework for incremental–decremental maximization that captures the gradual transformation or renewal of infrastructures. In our model, an initial solution is transformed one element at a time and the utility of an intermediate solution is given by the sum of the utilities of the transformed and untransformed parts. We propose a simple randomized algorithm and a more sophisticated deterministic algorithm, both of which find an order in which to transform the elements while maintaining a large utility during all stages of transformation, relative to an optimal solution for the current stage. More specifically, our algorithms yield competitive solutions for utility functions of bounded curvature and/or generic submodularity ratio, and, in particular, for submodular functions and functions satisfying the gross substitutes property. Our results show that incremental–decremental maximization is substantially more difficult than incremental maximization.
- 14 August 2026
- Published by Springer Nature in Acta Informatica
- Vol. 63 (3) , 31
Open AccessIncremental–decremental maximization
We introduce a framework for incremental–decremental maximization that captures the gradual transformation or renewal of infrastructures. In our model, an initial solution is transformed one element at a time and the utility of an intermediate solution is given by the sum of the utilities of the transformed and untransformed parts. We propose a simple randomized algorithm and a more sophisticated deterministic algorithm, both of which find an order in which to transform the elements while maintaining a large utility during all stages of transformation, relative to an optimal solution for the current stage. More specifically, our algorithms yield competitive solutions for utility functions of bounded curvature and/or generic submodularity ratio, and, in particular, for submodular functions and functions satisfying the gross substitutes property. Our results show that incremental–decremental maximization is substantially more difficult than incremental maximization.
- Open Access
- 12 August 2026
- Published by Elsevier in Games and Economic Behavior
- Vol. 159, 584-603
On the strategyproof allocation of items under a budget constraint
- 12 August 2026
- Published by Elsevier in Games and Economic Behavior
- Vol. 159, 584-603
Open AccessOn the strategyproof allocation of items under a budget constraint
- Open Access
- 12 August 2026
- Published by Springer Nature in Mathematical Programming
- p. 1-24
Generalized assignment and knapsack problems in the random-order model
We study different online optimization problems in the random-order model. There is a finite set of bins with known capacities and a finite set of items arriving in uniform random order. Upon arrival of an item, its size and its value for each of the bins is revealed and it has to be decided immediately and irrevocably to which bin the item is assigned, or whether the item is rejected. In this setting, an algorithm is $$\alpha $$ -competitive if the total expected value of all items assigned to the bins is at least an $$\alpha $$ -fraction of the total value of an optimal assignment that knows all items beforehand. We give an algorithm that is $$\alpha $$ -competitive with $$\alpha = (1-\ln 2 )/2 \approx 1/6.52$$ improving upon the previous best algorithm with $$\alpha \approx 1/6.99$$ for the generalized assignment problem and the previous best algorithm with $$\alpha \approx 1/6.65$$ for the integral knapsack problem. We then study the fractional knapsack problem where we have a single bin and it is also allowed to pack items fractionally. For that case, we obtain an algorithm that is $$\alpha $$ -competitive with $$\alpha = 1/e \approx 1/2.71$$ improving on the previous best algorithm with $$\alpha = 1/4.39$$ . We further show that the competitive ratio of 1/ e is best-possible for randomized algorithms in this model.- 12 August 2026
- Published by Springer Nature in Mathematical Programming
- p. 1-24
Open AccessGeneralized assignment and knapsack problems in the random-order model
We study different online optimization problems in the random-order model. There is a finite set of bins with known capacities and a finite set of items arriving in uniform random order. Upon arrival of an item, its size and its value for each of the bins is revealed and it has to be decided immediately and irrevocably to which bin the item is assigned, or whether the item is rejected. In this setting, an algorithm is $$\alpha $$ -competitive if the total expected value of all items assigned to the bins is at least an $$\alpha $$ -fraction of the total value of an optimal assignment that knows all items beforehand. We give an algorithm that is $$\alpha $$ -competitive with $$\alpha = (1-\ln 2 )/2 \approx 1/6.52$$ improving upon the previous best algorithm with $$\alpha \approx 1/6.99$$ for the generalized assignment problem and the previous best algorithm with $$\alpha \approx 1/6.65$$ for the integral knapsack problem. We then study the fractional knapsack problem where we have a single bin and it is also allowed to pack items fractionally. For that case, we obtain an algorithm that is $$\alpha $$ -competitive with $$\alpha = 1/e \approx 1/2.71$$ improving on the previous best algorithm with $$\alpha = 1/4.39$$ . We further show that the competitive ratio of 1/ e is best-possible for randomized algorithms in this model. - 1 May 2026
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 51 (2) , 1486-1513
Improved Bounds for Single-Nomination Impartial Selection
A randomized selection mechanism returns a probability distribution over individuals based on mutual nominations among them; it is impartial if the selection probability of each individual is independent of the nominations they cast and [ ]-optimal if the expected number of nominations received by the selected individual is always at least [ ] times that received by any individual. When individuals can cast multiple nominations, the permutation mechanism is [ ]-optimal, and this is the best possible. We show that the permutation mechanism does not provide the best possible factor in the natural situation when individuals cast exactly one nomination. Specifically, we provide a tight analysis of the permutation mechanism showing that it is [ ]-optimal in this case, and we design a new mechanism that is [ ]-optimal for [ ]. We further prove that no impartial mechanism can be better than [ ]-optimal. Funding: This research was supported by the Deutsche Forschungsgemeinschaft [Grant 431465007] and by the Engineering and Physical Sciences Research Council [Grant EP/T015187/1].
- 1 May 2026
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 51 (2) , 1486-1513
Improved Bounds for Single-Nomination Impartial Selection
A randomized selection mechanism returns a probability distribution over individuals based on mutual nominations among them; it is impartial if the selection probability of each individual is independent of the nominations they cast and [ ]-optimal if the expected number of nominations received by the selected individual is always at least [ ] times that received by any individual. When individuals can cast multiple nominations, the permutation mechanism is [ ]-optimal, and this is the best possible. We show that the permutation mechanism does not provide the best possible factor in the natural situation when individuals cast exactly one nomination. Specifically, we provide a tight analysis of the permutation mechanism showing that it is [ ]-optimal in this case, and we design a new mechanism that is [ ]-optimal for [ ]. We further prove that no impartial mechanism can be better than [ ]-optimal. Funding: This research was supported by the Deutsche Forschungsgemeinschaft [Grant 431465007] and by the Engineering and Physical Sciences Research Council [Grant EP/T015187/1].
- 17 March 2026
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 40 (1) , 349-373
Improved Approximation Algorithms for the Expanding Search Problem
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 each step, the searcher adds an edge to the solution, connecting an unexplored vertex to an explored one. The time required to add an edge equals its length. The objective is to minimize the weighted sum of exploration times for all vertices. We demonstrate that this problem is hard to approximate and present algorithms with improved approximation guarantees. Specifically, we provide a [Formula: see text]-approximation for any [Formula: see text] for the general case. On instances where the vertex weights are binary, we achieve a [Formula: see text]-approximation. Finally, we develop a polynomial-time approximation scheme for Euclidean graphs. Previously, only an 8-approximation was known for all these cases.
- 17 March 2026
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 40 (1) , 349-373
Improved Approximation Algorithms for the Expanding Search Problem
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 each step, the searcher adds an edge to the solution, connecting an unexplored vertex to an explored one. The time required to add an edge equals its length. The objective is to minimize the weighted sum of exploration times for all vertices. We demonstrate that this problem is hard to approximate and present algorithms with improved approximation guarantees. Specifically, we provide a [Formula: see text]-approximation for any [Formula: see text] for the general case. On instances where the vertex weights are binary, we achieve a [Formula: see text]-approximation. Finally, we develop a polynomial-time approximation scheme for Euclidean graphs. Previously, only an 8-approximation was known for all these cases.
- Open Access
Impartial Selection with Predictions
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 selected, they may be incentivized to misrepresent their true opinion about the eligibility of others to influence their own chances of selection. Impartial mechanisms circumvent this issue by guaranteeing that the selection of an agent is independent of the nominations cast by that agent. Previous research has established strong bounds on the performance of impartial mechanisms, measured by their ability to approximate the number of nominations for the most highly nominated agents. We study to what extent the performance of impartial mechanisms can be improved if they are given a prediction of a set of agents receiving a maximum number of nominations. Specifically, we provide bounds on the consistency and robustness of such mechanisms, where consistency measures the performance of the mechanisms when the prediction is accurate and robustness its performance when the prediction is inaccurate. For the general setting where up to $k$ agents are to be selected and agents nominate any number of other agents, we give a mechanism with consistency $1-O\big(\frac{1}{k}\big)$ and robustness $1-\frac{1}{e}-O\big(\frac{1}{k}\big)$. For the special case of selecting a single agent based on a single nomination per agent, we prove that $1$-consistency can be achieved while guaranteeing $\frac{1}{2}$-robustness. A close comparison with previous results shows that (asymptotically) optimal consistency can be achieved with little to no sacrifice in terms of robustness.Open AccessImpartial Selection with Predictions
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 selected, they may be incentivized to misrepresent their true opinion about the eligibility of others to influence their own chances of selection. Impartial mechanisms circumvent this issue by guaranteeing that the selection of an agent is independent of the nominations cast by that agent. Previous research has established strong bounds on the performance of impartial mechanisms, measured by their ability to approximate the number of nominations for the most highly nominated agents. We study to what extent the performance of impartial mechanisms can be improved if they are given a prediction of a set of agents receiving a maximum number of nominations. Specifically, we provide bounds on the consistency and robustness of such mechanisms, where consistency measures the performance of the mechanisms when the prediction is accurate and robustness its performance when the prediction is inaccurate. For the general setting where up to $k$ agents are to be selected and agents nominate any number of other agents, we give a mechanism with consistency $1-O\big(\frac{1}{k}\big)$ and robustness $1-\frac{1}{e}-O\big(\frac{1}{k}\big)$. For the special case of selecting a single agent based on a single nomination per agent, we prove that $1$-consistency can be achieved while guaranteeing $\frac{1}{2}$-robustness. A close comparison with previous results shows that (asymptotically) optimal consistency can be achieved with little to no sacrifice in terms of robustness.