Two Holes Make a Difference: Deterministic Paging with Delay and Deadlines

Darya Melnyk, Linda Thelen, Yuyi Wang

In this paper, we study online paging with delay or deadlines. In online paging with delay, an online algorithm manages a cache of size $k$ and needs to serve incoming requests by…