2
$\begingroup$

In a caching problem, items arrive online, and the algorithm needs to decide which elements to keep in the cache. If the current item is not cached, we pay a penalty of $1$.

It is well known that for a $k$-sized LRU cache has a competitive ratio of $k$ and that no deterministic algorithm can do better than that.

Consider the following (randomized) algorithm:

  1. We choose a random hash function that maps items into $\{1,\ldots,d\}$.
  2. Whenever we see a request, we hash it into one of $d$ LRU caches (of size $k/d$ each).

What is the competitive ratio of this limited associativity LRU variant?


It seems that if $k\gg d$, we can use a balls-and-bins analysis to show that an input that consists of round robin of $k$ items will give a $k/d (1-o(1))$ lower bound.

  • Is this tight?
  • What about other cases?
$\endgroup$
  • $\begingroup$ No, it's not competitive as is. Consider the case of k items that are requested repeatedly in round-robin fashion. Clearly OPT has constant cost. But with positive probability one of your d caches will receive more than k/d items, and so will fault repeatedly. (I guess you need to use a slightly larger cache than OPT. It seems difficult to ensure that your hash function partitions any set of k items into d groups of size k/d.) $\endgroup$ – Neal Young Jan 14 at 23:46
  • $\begingroup$ @NealYoung - good point. $\endgroup$ – R B Jan 15 at 2:26

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.