In the paging problem, we have a cache of size $k$ and a universe of $n>k$ pages.

In an online setting, we get requests for pages $p_1,p_2,\ldots p_t$, and are required to have page $p_i$ loaded at the cache at time $i$.

Our goal is to minimize the load cost; that is, we pay a cost every time a page is loaded into the cache, and thus we aim to maximize the "cache hits".

In the unweighted case, where each load costs 1, the LRU algorithm achieves a competitive ratio (CR) of $k$, which is known to be optimal for deterministic algorithms.

Next, consider the weighted case, where each page $i$ has a loading cost of $c_i$, and the goal is to minimize the sum of loading costs.

There are known algorithms for this problem which also achieve a CR of $k$, but I couldn't find this next algorithm, and was wondering what's its CR (especially since its much simpler than the two algorithms I know which achieve a $k$ competitive ratio).

  • We initialize a "marking" bit for each cached page to be $0$.
  • Upon request for a cached page, set its bit to $1$.
  • Upon request for an uncached page, evict the smallest weight page with bit $0$ from the cache, and insert the arriving one with bit $1$.
  • If all of the cache bits are $1$, set them all to $0$.

    What is the competitive ratio of the above algorithm?

  • $\begingroup$ Why a downvote without a comment :( ? $\endgroup$ – user47256 Mar 3 '16 at 8:38
  • 2
    $\begingroup$ What are your thoughts? Do you have a guess? Have you tried proving it? You can start with the simplest case, $k=2$, which should be easy to analyze. $\endgroup$ – Yuval Filmus Mar 3 '16 at 16:56
  • 2
    $\begingroup$ Did you come up with this algorithm yourself, or is it a homework or self-study problem? $\endgroup$ – Yuval Filmus Mar 3 '16 at 16:57

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.