Mittagsseminar (by J. Lengler, K. Bringmann, B. Gärtner, M. Hoffmann, R. Kyng, D.Steurer, V. Traub)

Date and Time: Thursday, August 21, 2025, 12:15 pm

Duration: 30 minutes

Location: OAT S15

Speaker: Lukas Himmelreich

The Risk-Sensitive Bahncard Problem: Competitive and Learning-Augmented Algorithms

Traditional online algorithms typically optimize expected cost, but can perform poorly in settings where rare but very costly events can occur, such as in energy-related applications. Motivated by this challenge, we study the design of risk-sensitive algorithms for the online Bahncard problem. We begin by presenting a family of closed-form algorithms that obtain a provable bound on a risk-sensitive performance metric known as the Conditional Value at Risk (CVaR)-competitive ratio. Under a simplifying structural restriction, we show how to design an improved strategy that results from the solution of a certain delay differential equation. Furthermore, we show that this structural assumption can be relaxed, yielding an implicit characterization of the optimal online algorithm which can be solved numerically on an instance-by-instance basis. We also consider the design of learning-augmented algorithms in this risk-sensitive setting, where the decision-maker receives a potentially inaccurate prediction about the problem instance. In this setting, we design a family of algorithms that, for λ ∈ (0, 1] achieves Θ(λ)-consistency---thus ensuring good performance if the prediction is accurate---while maintaining a risk-sensitive robustness of Θ(1/λ), ensuring strong worst-case guarantees. To conclude, we perform a case study on the problem of peak-aware economic dispatching in microgrids, comparing our risk-sensitive learning-augmented algorithm against the state-of-the-art learning-augmented algorithm designed to optimize expected cost. Our results highlight the advantages of risk-sensitive algorithm design, which can mitigate tail costs while maintaining strong average-case performance.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2026  2025  2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login