Homework 19

Due Friday, April 24 at 7:00 PM. Please refer to the homework policy here. $\newcommand{\groundset}{\mathcal{N}}$

Problems

1. In the video, we showed that an LRU cache is $k$-competitive w/r/t an optimal cache of the same size $k$. Here we will go for a slightly different "bicriteria" bound. Let $\ell < k$. Show that an LRU cache of size $k$ is $k/(k + 1-\ell)$-competitive with any optimal cache of size $\ell$.

That means, for example, that an LRU cache of size $k$ is 2-competive with any cache of size $k/2$. Some people find this bound more compelling.

You should be able to prove this by a short modification of the argument of the $k$-competive bound. It suffices to point out just which part of the argument should change, and how.