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 lie 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.

Teaching

This winter I organize the lab course on Algorithmic Battle and support Prof. Rossmanith in the master's lecture Analysis of Algorithms.

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

Seminar Online Algorithms in Summer 2021 and 2025,
Lab Course Algorithmic Battle in Winter 2021, 2022, 2023 and 2024,
Basic Lecture Datastructures and Algorithms in Summer 2021 and 2024,
Seminar Decision Theory in Summer 2023,
Basic Lecture Formal systems, automatons and processes in Summer 2022 and 2023,
Seminar Dynamic Algorithms in Summer 2022,
Proseminar Certifying Algorithms in Summer 2022,
Lab Course Competitive Programming in Teams in Summer 2022 and 2023,
Seminar Proof from the Book in Winter 2021,
Seminar Helping Donald Knuth in Winter 2021,
Lecture Complexity Theory in Winter 2020,
Basic Lecture Microeconomics in Summer 2018, 2019 and 2020,
Basic Lecture 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 received 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

So far, I supervised the following 15 sucessful thesis bachelor's or master's thesis projects:

"Fog of War Chess" by Julius Stannat
"The Removable Online Simple Knapsack Problem with Extended Reservation" by Julian Behrmann
"The Online Feedback Vertex Set Problem" by Chris Degrand
"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

In addition, you might have seen my poster at Highlights of Algorithms 2025, or 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, the PhD School of Algorithms and Machine Learning, 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.

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").