A Toolbox for Online Algorithms
Lecturer:
Marcin Bienkowski
(Institute of Computer Science, Wroc³aw University).
About the lecturer | Course Summary | Slides and Exercises | Assignment
About the lecturer:
Marcin Bienkowski received his PhD from the University of Paderborn, Germany, and is currently an assistant professor at the University of Wroclaw. His research interests concentrate on design and analysis of online algorithms for network problems. He published over 20 papers on these topics and is the winner of Witold Lipski prize for Young Researchers in Computer Science.
Course summary: Many real-life applications, ranging from caching and scheduling to navigation and currency trading, require online solutions. In this setting, algorithms learn the input sequence gradually and have to produce parts of the output immediately, without the knowledge about future demands or requests. Theoreticians usually measure the performance of such solutions by comparing their cost to the cost of an optimal solution (which knows the whole input in advance). Despite its deficiencies, in the last 25 years, this type of competitive analysis became the standard yardstick used by the TCS community and also gained acceptance in some applied areas. In this mini-course, I will cover some generic approaches of attacking online problems, such as potential functions, primal-dual scheme, online randomized rounding, classify and randomly select method, and - last but not least - work functions. I will concentrate on the techniques, and therefore during the course apply these tools to toy problems. No prior knowledge about the competitive analysis is assumed from the attendees.
Exercises: exercises.pdf
Slides: slides.pps (1.4M)
Notes: slides.pps
Assignment: exam.pdf (due: 28th April)