Matthias Gehnen

E-mail:	gehnen@cs.rwth-aachen.de
Office:	Room 4105b, Erweiterungsbau E1 of the Computer Science Center (2353|105b)
Office hours:	Usually Tuesday 12:00-13:00, check this calender to see whether it takes place
Phone:	+49-241-80-21132

Currently, I am a doctoral resercher in the Theoretical Computer Science group.

Research

My main research interest in my PhD studies is within the field of online algorithms.
I mainly studied two variants that ly in between the classical offline and online settings:

• Sometimes one needs to make a decision without knowing everything necessary. Often, e.g. when buying a train ticket or booking a hotel room, there are multiple options: you could buy a ticket immediately and without the option to cancel it, or you could delay the decision for some time - by buying a ticket which allows cancellation or by waiting for some more time. However, delaying this decision usually corresponds to a higher price.
  Depending on your situation and the surcharge: Is it worth it to delay the decision?
  This can be modeled within the Reservations setting.
• Some situations require making decisions, but luckily in most cases they do not need to be made in complete darkness: While it is unrealistic to assume that one has the full knowledge about everything relevant, it is similarly unrealistic to assume that no information is available. You might have experience with what is coming or some machine-learning tool might give you an estimate. You may even have measured everything, but do not have the exact values due to rounding issues or imprecise tools.
  So given the precision of your estimates: How much does it help you?
  This is the setting of online algorithms with Estimates.

Open Problems

There are two problems on which I spent a decent amount of time thinking about, but have not found a satisfying answer:

• The Online Feedback Vertex Set can be understood as a graph that is presented iteratively, and every time a cycle appears, you have to delete a vertex such that the graph gets cycle-free again. Even though this is a very natural problem, to the best of my knowledge it has not been studied extensively yet.
  I found out that the competitive ratio can be lower bounded by 4 and that there is a 5-competitive algorithm, but there still remains a gap (see "Delaying Decisions and Reservation Costs").
• You are given a graph and the promise that every edge has weight 1 or 2. You now have to find a travelling salesman tour, but each edge weight gets revealed to be either 1 or 2 when your agent is on a vertex incident to it (as in Graph Exploration). What is the best competitive ratio you can achieve?
  Clearly a ratio of 2 is possible by precomputing a tour, which is optimal if every weight is announced to be either x or 2x for different x. On the restricted case with weights 1 or 2 I believe a ratio of 1.5 might be achievable (see "Graph Exploration with Edge Weight Estimates").

Teaching

This summer I organize a seminar on Online Algorithms.

In the past, I worked in various ways for the following courses:

• Algorithmic Battle in Winter 2021, 2022, 2023 and 2024,
• Datastructures and Algorithms in Summer 2021 and 2024,
• Decision Theory in Summer 2023,
• Formal systems, automatons and processes in Summer 2022 and 2023,
• Dynamic Algorithms in Summer 2022,
• Certifying Algorithms in Summer 2022,
• Competitive Programming in Teams in Summer 2022 and 2023,
• Proof from the Book in Winter 2021,
• Helping Donald Knuth in Winter 2021,
• Current Topics in Online Algorithms in Summer 2021,
• Complexity Theory in Winter 2020,
• Microeconomics in Summer 2018, 2019 and 2020,
• Analysis for Computer Scientists in Winter 2017.

In 2022 and 2023 I led the RWTH-team at the International Mathematics Competition. Furthermore, organized the Competitive Programming Contest at RWTH Aachen.

In particular, I am proud of our lab course Algorithmic Battle, which I have hosting in recent years.
Its unique teaching concept allows students to find out themselves what makes a problem hard in various settings, and furthermore lets participants experience the importance of rigorous testing when developing code. We got supported by funding from a Freiraum Grant by Stiftung Innovation in der Hochschullehre and a grant within the ICON ENHANCE Call 2025 for further development of this lab and its concept.

Supervised Theses

The following thesis projects were completed already:

• "Online Travelling Salesperson Problem with Bounded Predictions" by Emilie Tröll
• "A Variant of the Online Travelling Salesperson Problem" by Anna Hansson
• "Online Broadcast with and without Advice" by Jannis Grosse-Verspohl
• "Time Analysis of Space Efficient Uniform Partitioning in Population Protocols " by Pascal Sahner
• "Online Knapsack with Removal and Predictions " by Kübra Güven
• "Balancing Risk and Reward - a Secretary Problem Variant with Reservations and cost-free Option" by David Frason
• "Online Tetris" by Luca Venier
• "Online Bin Packing with Estimated Item Sizes" by Andreas Usdenski
• "The Postdoc Problem with Reservation Costs " by Christian Mürtz
• "The Secretary Problem with Reservation Costs and Accepting one of the two best Candidates" by Jakob Junck
• "The Postdoc Variant of the Secretary Problem with Reservation Costs" by Mats Bierwirth
• "Pitch Detection Methods for Automatic Music Transcription" by Magnus Groß: here you can access the code of his practical part

Preprints, Publications and Talks

• Online Bin Packing with Item Size Estimates, Preprint available.
• Online Knapsack Problems with Estimates at MFCS 2025.
• Online General Knapsack with Reservation Costs, Preprint available.
• Graph Exploration with Edge Weight Estimates, Preprint available.
• Online Unbounded Knapsack at Theory of Computing Systems 2025.
• Tree Coloring: Random Order and Predictions, Preprint available.
• Online Tetris is not competitive at FUN 2024.
• Online Simple Knapsack with Bounded Predictions at STACS 2024.
• Delaying Decisions and Reservation Costs at COCOON 2023.
• The Online Simple Knapsack Problem with Reservation and Removability at MFCS 2023.
• Transitive Avoidance Games on Boards of Odd Size in The Electronic Journal of Combinatorics, Issue 4 (2021).
• The Secretary Problem with Reservation Costs at COCOON 2021.

In addition, you might have seen my talks at the Workshop on Recent Trends in Online Algorithms (ICALP 2023), the Dutch Day on Optimization 2023, the Seminar on Graphs and Optimization at LaBRI, or here in Aachen.

Personal Scholarships and Awards

• A Research ENHANCE.R grant of 20.000 Euros to fund my research on Online Algorithms with Estimates March 2025.
• Idea League Research Grant for a research stay at the Group for Algorithms and Didactics at ETH Zürich in February and March 2023.
• Springorum-Denkmünze in 2021.
• Part of the Dean's List of the faculty for my studies in mathematics.
• Funding of my studies by the Studienstiftung des deutschen Volkes starting in 2016.

Studies

Before starting in the Theory Group, I studied mathematics with minors in economics and computer science at RWTH Aachen University. I obtained my master's degree with honors in December 2020.

---