There has been growing recent interest in improving analysis of online algorithms by exploiting extra knowledge about the future. Several new models have been proposed leading to the development of learning-augmented algorithms and semi-online algorithms. In this talk, I'll give a brief overview of recent developments in this area using the ski-rental problem as an illustrative example. In the second half of the talk, I'll introduce a new model for the classical paging problem called interleaved caching that aims to model request sequences in multitasking systems with a shared cache and provide tight upper and lower bounds on the competitive ratio.

 

This is joint work with Ravi Kumar, Zoya Svitkina, and Erik Vee.