Algorithm GreedyDual
Handles uniform-size, differing-cost pages
- Associate a value H with each page P, initially H=cost(P)
- Replace the page with min_H; subtract min_H from all cached pages’
- If page P is accessed again, restore H to cost(P)
Combines locality with cost considerations
Proved to be online optimal