It can be proven that GreedyDual-Size is online-optimal. For any sequence of accesses to documents with arbitrary sizes and arbitrary costs, the cost of cache misses under GreedyDual-Size is at most k times that under the offline optimal replacement algorithm, where k is the ratio of the cache size to the size of the smallest page. The ratio is the lowest achievable by any online replacement algorithm. Below is a proof of the following theorem which establishes the online-optimality of GreedyDual-Size.
Neal Young proved in [You91b] that Greedy Dual for pages of uniform size is k-competitive. We prove here that the version which handles pages of multiple size is also k-competitive. (In both cases, k is defined to be the ratio of the size of the cache to the size of the smallest page). The proof below is based on a proof that another algorithm called BALANCE which also solves the multi-cost uniform-size paging problem is k-competitive [CKPV91].
All of the above bounds are tight, since we can always assume that all pages are as small as possible and have the same cost and invoke the lower bound of k on the competitive ratio for the uniform-size uniform-cost paging problem found in [ST85].
It should also be noted that the same bound can be proven for the version of the algorithm which uses c(p) instead of c(p)/s(p) in the description of the algorithm in Figure 5. Young has independently proven a generalization of the result below [You97]. The generalization covers the whole range of algorithms described in his original paper [You91b] instead of the particular version covered here.