Graduate seminar (S4C3): Learning-augmented algorithms

Learning-augmented algorithms have recently emerged as a rapidly growing and active research direction. It seeks to combine the reliability of worst-case algorithm design with the practical power of machine-learned advice. The central question is how predictions about future requests, input structure, optimal solutions, or dual variables can improve classical competitive or approximation guarantees, while still maintaining robustness when the predictions are wrong.
In this seminar, we will cover a sequence of foundational and recent papers in this area, with a particular focus on their applications to combinatorial optimization. We will see how predictions can be used to improve competitive ratios in online algorithms, approximation ratios for NP-hard optimization problems, and running times for classical graph algorithms.

You can find the slides from the planning meeting here.