The Longest Forward Distance algorithm (LFD) for the paging problem.

LFD is defined as follows.  Let x be the current request.

1.  If x is in the cache, do nothing.
2.  If x is not in the cache, copy x into the cache, and eject that
page whose next request is farthest in the future.  In case two or
more cache pages are never requested in the future, eject one of those
arbitrarily.

Theorem 1: LFD is optimal.  I will not give a proof here.

Local Optimality.  We can say that an offline algorithm A is "locally
optimal" if, after any number of steps, A is optimal for the sequence
of requests so far.

Local Optimality Hypothesis (LOH):  There exists a locally optimal
offline algorithm.

Theorem 2: LFD is locally optimal for the paging problem.

That is to say, if rho = r_1 r_2 .... r_N, then LFD, looking at the entire
sequence, is still optimal for the truncated sequence r_1 ... r_M for any M.

Problem: Does LOH hold for every online problem?

Example.  Suppose k = 2, and the request sequence is (ab)cabdefbac.
My notation indicates that the initial cache is (ab) and that the actual
request sequence is cabdefb.

After step 1, the LFD cache is (ca).
After step 2, the LFD cache is (ab).
After step 3, the LFD cache is (ba).  (I use the rule that the mru is first)
After step 4, the LFD cache is (db).
After step 5, the LFD cache is (eb).
After step 6, the LFD cache is (fb).
After step 7, the LFD cache is (bf).
After step 8, the LFD cache is (ab) or (af).  (There is an arbitrary choice.)
After step 9, the LFD cache is (ca), (cb), or (cf).  (Do you see why?)

The total cost of LFD is 7, which is optimal for this sequence.
But what about the situation after 6 steps?  At that time, LFD has
paid 5.  Could some other offline algorithm service the first 6 steps
at smaller cost?  The answer is no:  5 is the optimal cost for the
request sequence (ab)cabdef.

Now look at it from the point of view of an online observer, i.e., someone
who only knows the past requests, but realizes that there might be future
requests.  After one step, the online observer knows that LFD's cache is
either (ca) or (cb), but cannot determine which.  But after 2 steps, the
online observer knows that LFD's cache is (ac).

After 6 steps, the online observer knows that LFD's cache must be
(fa), (fb), (fc), (fd), or (fe).  After 7 steps, the online observer, once
again, knows LFD's cache for sure.

Problem: Show that there exists an optimal offline algorithm for the
paging problem for k = 2 which does not satisfy LOH.  Hint: look at the
request sequence (ab)cba.