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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.