# Competitive ratio of this paging algorithm

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?

• Why a downvote without a comment :( ? – user47256 Mar 3 '16 at 8:38
• 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. – Yuval Filmus Mar 3 '16 at 16:56
• Did you come up with this algorithm yourself, or is it a homework or self-study problem? – Yuval Filmus Mar 3 '16 at 16:57