Paging with Succinct Predictions
Antonios Antoniadis,u00a0Joan Boyar,u00a0Marek Elias,u00a0Lene Monrad Favrholdt,u00a0Ruben Hoeksma,u00a0Kim S. Larsen,u00a0Adam Polak,u00a0Bertrand Simon
Paging is a prototypical problem in the area of online algorithms. It has also played a central role in the development of learning-augmented algorithms. Previous work on learning-augmented paging has investigated predictions on (i) when the current page will be requested again (reoccurrence predictions), (ii) the current state of the cache in an optimal algorithm (state predictions), (iii) all requests until the current page gets requested again, and (iv) the relative order in which pages are requested. We study learning-augmented paging from the new perspective of requiring the least possible amount of predicted information. More specifically, the predictions obtained alongside each page request are limited to one bit only. We develop algorithms satisfy all three desirable properties of learning-augmented algorithms u2013 that is, they are consistent, robust and smooth u2013 despite being limited to a one-bit prediction per request. We also present lower bounds establishing that our algorithms are essentially best possible.
