Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Online Weighted Paging with Distributions
event speaker icon
Tomer Tsachor (M.Sc. Thesis Seminar)
event date icon
Wednesday, 09.08.2023, 11:00
event location icon
Zoom Lecture: 3906204304 and Taub 401
event speaker icon
Advisor: Prof. Joseph Naor
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.