In this course, we will study the *algorithms with predictions* or *learning-augmented algorithms* that have gained a substantial amount of attention in recent years. In this algorithmic framework, we are additionally given a possibly imperfect prediction as input, and want to devise an algorithm utilizing this prediction with the following three guarantees:
- if the prediction happens to be accurate, we want the algorithm to perform very well, or even optimally;
- even if the prediction happens to be very poor, we still want the algorithm to perform not much worse than when we solve the problem without the prediction;
- as the "error" of the prediction increases, we want the performance of the algorithm to gradually decrease.
This framework has affected a wide range of research fields in theoretical computer science, including (but not limited to) data structures, algorithmic game theory, and in particular online optimization.
Since the field emerged very recently, there doesn't exist a textbook yet (to the best of my knowledge). Instead, we would follow a survey paper giving a gentle introduction to this field:
- Mitzenmacher, M., & Vassilvitskii, S. (2022). Algorithms with predictions. *Communications of the ACM*, 65(7), 33-35.
We will then select some fundamental results in the field from the paper list [[link]](https://algorithms-with-predictions.github.io/) maintained by Alexander Lindermayr and Nicole Megow (University of Bremen). A (tentative) list of topics that will be covered in the course, with an emphasis on online optimization, is:
- ski rental,
- online set cover,
- caching/paging,
- online bipartite matching,
- bloom filter, and
- Hungarian algorithm.
This course is planned to be **half-semester**, in the *first half of summer* starting in late February, and **lecture-intensive**, while the students are expected to take an *oral examination* or submit a *term paper* at the end of the course.
