Exchange argument in Greedy Algorithms

Recently I started reading this algorithm textbook for my CS330 class next semester – Algorithm Design by Jon Kleinberg and Eva Tardos. Today I am going to record my thoughts on Chapter 4.3 – Exchange argument.

Exchange argument is actually the name of a method used to prove a type of greedy algorithm. The question that we focus on is as follows: Suppose there is a computer with limited cache memory, and we need to process a sequence of data from the main memory. What is the best order to “evict” certain data and retrieve data from the main memory so that the total number of times we evict (misses) is the least?

According to Les Belady, the best way to do this is to evict the “farthest-in-the-future” item in the cache memory. For example, consider a sequence like a b c d a d e a d b c and a cache memory of size 3 with initially a b c in it. The best plan is to evict c at step 4 becuase it is “farthest-in-the-future”.

The proof uses the method of “exchange argument”, in which we first suppose the best way to do this, say S, and our plan, say S*, and we revise our plan so that it eventually is identical to S, in the meantime follows our “farthest-in-the-future” rule.

Assume the first j steps of S and S* are identical, so now we have the same sequence of data in cache memories. For the (j + 1)st step, say S evicts the item e but S* evicts f since f is farthest. We would like S* to “come back” to S as soon as possible and avoid adding any more misses. Now consider the (j + 2)nd request.

If there is a request to item g which is not equal to either e or f:

If S evicts any item other than f, we would simply let S* also evict that item. After this step two cache memories would be identical, job done. Else, S evicts f, we would let S* evict e. In this way two cache memories are again identical. Hooray.

Else, there is a request to e:

Note that S*’s cache memory now contains e. If S evicts f, two cache memories are now equal. If S evicts some f’ other than f instead, we would also let S* evict f’, and bring f, then again voila.

There can’t be a request to f before to e because we already know f is farther than e.

The proof above is not complete, but the spirit is shown: first assume we have the best solution, and try to prove that our solution is the best by closing the gap. Quite amazing.

Leave a Reply

Your email address will not be published. Required fields are marked *