Ola Svensson - “Learning-Augmented Online Algorithms and the Primal-Dual Method“ | MoCCA’20

The talk “Learning-Augmented Online Algorithms and the Primal-Dual Method“ by Ola Svensson on the Moscow Conference on Combinatorics and Applications at MIPT. Annotation: The design of learning-augmented online algorithms is a new and active research area. The goal is to understand how to best incorporate predictions of the future provided e.g. by machine learning algorithms that rarely come with guarantees on their accuracy. In the absence of guarantees, the difficulty in the design of such learning-augmented algorithms is to find a good balance: on the one hand, following blindly the prediction might lead to a very bad solution if the prediction is misleading. On the other hand, if the algorithm does not trust the prediction at all, it will simply never benefit from an excellent prediction. An explosion of recent results solve this issue by designing smart algorithms that exploit the problem structure to achieve a good trade-off between these two cases. In this talk, we will discus