The Taub Faculty of Computer Science Events and Talks

We study the classic problem of online weighted paging with a probabilistic prediction model, in which we are given additional information about the input in the form of distributions overpage requests, known as distributional online paging (DOP). Our main result is an efficient online algorithm that achieves a constant factor competitive ratio with respect to the best online algorithm (policy) for weighted DOP.

Our starting point is a linear programming formulation for weighted DOP. Unfortunately, this formulation has a large integrality gap which depends on page weights. In our work we overcome the integrality gap by incorporating an additional rounding step based on dynamic programming, achieving the desired constant competitive factor algorithm for the problem.