Nikhil Bansal
Online algorithms for Generalized Caching

The generalized caching problem is an extension of the classic online
caching problem, where the pages can  have both arbitrary sizes and
arbitrary fetch costs. In particular, there is a cache and a collection
of pages. Requests for pages arrive in an online manner. If the requested
page is already present in the cache, we do nothing, otherwise we need
to fetch the requested page into the cache possibly evicting other
pages. The goal is to minimize the total fetch cost.

Prior to our work, no sublinear competitive algorithms were known for
the problem.  In this talk I will describe a randomized poly-logarithmic
competitive algorithm based on the recent primal dual technique for
online algorithms. The talk is completely self-contained and will not
assume any prior knowledge.


Joint work with Niv Buchbinder and Seffi Naor.