Martin Knaack

 

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: TEL 509
Telephone: +49 30 314 19002983
Email: (lastname)@math.tu-berlin.de

Teaching

• 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

to appear

• 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$.

2022

• 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$.