# ICS 269, Fall 2004: Theory Seminar

## 19 Nov 2004:

Caching with Expiration Times

Authors:
Parikshit Gopalan , Howard Karloff , Aranyak Mehta , Milena Mihail ,
Nisheeth Vishnoi

Speaker:
Michael Shindler

From:
Proceedings 13th ACM-SIAM Symp. on Discrete Algorithms (SODA),
January 6-8, 2002, San Francisco, pp.540-547.
The authors investigate the effects of caching when
dealing with both access frequency and expiration times, using the
common least-recently used algorithm as a starting point. They present
and analyze three different classes of algorithms for dealing with the
problem. There exist deterministic marking algorithms that are
competitive relative to the size of the cache. They also discuss
randomized marking algorithms and the optimal offline algorithm.