Martin Knaack

PhD student

Fakultät II - Mathematik und Naturwissenschaften
Institut für Mathematik, Secr. MA 5-2
Technische Universität Berlin
Straße des 17. Juni 136
10623 Berlin

Office: MA 661
Telephone: n/a
Email: (lastname)@math.tu-berlin.de

Teaching

Teaching assistant for the lecture Discrete Optimization (ADM II)
Summer 2025
Teaching assistant for the lecture Computerorientierte Mathematik II
Summer 2024
Teaching assistant for the lecture Computerorientierte Mathematik I
Winter 23/24
Teaching assistant for the lecture Computerorientierte Mathematik II
Summer 2023
Teaching assistant for the lecture Computerorientierte Mathematik I
Winter 22/23
Teaching assistant for the lecture Computerorientierte Mathematik II
Summer 2022
Teaching assistant for the lecture Computerorientierte Mathematik I
Winter 21/22
Teaching assistant for the lecture Discrete Optimization (ADM II)
Summer 2021

Publications

Packing a Knapsack with Items Owned by Strategic Agents (Javier Cembrano, Max Klimm, and Martin Knaack)
WINE 2024 – Proc. 20th Conference on Web and Internet Economics.
Bibtex Abstract
@inproceedings{CembranoKlimmKnaack2024,
author = {Javier Cembrano and Max Klimm and Martin Knaack},
title = {Packing a Knapsack with Items Owned by Strategic Agents},
booktitle = {WINE 2024 – Proc. 20th Conference on Web and Internet Economics},
year = {to appear},
}

This paper considers a scenario where a mechanism designer is interested in selecting items with maximum total value under a knapsack constraint. The items, however, are controlled by strategic agents who aim to maximize the total value of their items in the knapsack. This is a natural setting, e.g., when agencies select projects for funding, companies select products for sale in their shops, or hospitals schedule MRI scans for the day. A mechanism governing the packing of the knapsack is strategyproof if no agent can benefit from hiding items controlled by them to the mechanism. We are interested in mechanisms that are strategyproof and $\alpha$-approximate in the sense that they always approximate the maximum value of the knapsack by a factor of $\alpha \in [0,1]$. First, we give a deterministic mechanism that is $\smash{\frac{1}{3}}$-approximate. For the special case where all items have unit density, we design a $\smash{\frac{1}{\phi}}$-approximate mechanism where $1/\phi \approx 0.618$ is the inverse of the golden ratio. This result is tight as we show that no deterministic strategyproof mechanism with a better approximation exists. We further give randomized mechanisms with approximation guarantees of $1/2$ for the general case and $2/3$ for the case of unit densities. For both cases, no strategyproof mechanism can achieve an approximation guarantee better than $1/(5\phi -7)\approx 0.917$.

Generalized Assignment and Knapsack Problems in the Random-Order Model (Max Klimm and Martin Knaack)
IPCO 2025 – Proc. 26th Conference on Integer Programming and Combinatorial Optimization, pp. 341–354.
pdf doi Bibtex Abstract
@inproceedings{KlimmKnaack2025,
author = {Max Klimm and Martin Knaack},
title = {Generalized Assignment and Knapsack Problems in the Random-Order Model},
booktitle = {IPCO 2025 – Proc. 26th Conference on Integer Programming and Combinatorial Optimization},
pages = {341--354},
doi = {10.1007/978-3-031-93112-3_25},
year = {2025},
}

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. 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 to not assign the item at all. In this setting, an algorithm is $\alpha$-competitive if the total 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 this competitive ratio is the best-possible for this model.

Supersonic Overland Without a Sonic Boom: Quantitative Assessment of Mach-Cutoff Flight (Bernd Liebhardt, Florian Linke, and Martin Knaack)
Journal of Aircraft, 59(5):1257-1266, 2022.
doi Bibtex Abstract
@article{LiebhardtLinkeKnaack,
author = {Bernd Liebhardt and Florian Linke and Martin Knaack},
title = {Supersonic Overland Without a Sonic Boom: Quantitative Assessment of Mach-Cutoff Flight},
journal = {Journal of Aircraft},
volume = {59},
number = {5},
pages = {1257-1266},
year = {2022},
doi = {10.2514/1.C036637},
}

When flying at low supersonic speeds, rising temperatures and convenient winds can deflect the sonic boom shock waves so that they do not reach the ground. This work presents a computation methodology that incorporates atmospheric sonic ray tracing, topography, and realistic three-dimensional atmospheres in order to optimize supersonic overland cruise with respect to speed. Flight missions are simulated on several suitable city pairs using numerous atmospheric conditions. Flight times and fuel consumption are compared to subsonic high-speed missions.
Maximizing a Submodular Function with Bounded Curvature Under an Unknown Knapsack Constraint (Max Klimm and Martin Knaack)
APPROX 2022 – Proc. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems.
PDF doi Bibtex Abstract
@inproceedings{KlimmKnaack2022,
author = {Max Klimm and Martin Knaack},
title = {Maximizing a Submodular Function with Bounded Curvature Under an Unknown Knapsack Constraint},
booktitle = {APPROX 2022 – Proc. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems},
year = {2022},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.49},
}

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 pack next based on the past packing history. The robustness factor of a policy is the worst case ratio of the solution obtained by following the policy and an optimal solution that knows the knapsack capacity. We develop an algorithm with a robustness factor that is decreasing in the curvature $c$ of the submodular function. For the extreme cases $c = 0$ corresponding to a modular objective, it matches a previously known and best possible robustness factor of $1/2$. For the other extreme case of $c = 1$ it yields a robustness factor of $\approx 0.35$ improving over the best previously known robustness factor of $\approx 0.06$.

Recent Talks

Generalized Assignment and Knapsack Problems in the Random-Order Model, IPCO 2025, 11. Jun 25
Generalized Assignment and Knapsack Problems in the Random-Order Model, 15th Day On Computational Game Theory, 07. Mar 25
Packing a Knapsack with Items Owned by Strategic Agents, WINE 2024, 04. Dec 24
Improved Bounds for Selfish Knapsack, 14th Day on Computational Game Theory, 08. Mar 24
Maximizing a Submodular Function with Bounded Curvature under an Unknown Knapsack Constraint, International Conference on Operations Research, 31. Aug 23
Maximizing a Submodular Function with Bounded Curvature under an Unknown Knapsack Constraint, APPROX 2022, 21. Sep 22

Martin Knaack

Teaching

Publications

to appear

2025

2022

Recent Talks