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".
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?