CMSC 39600 Online Algorithms Adam Kalai Sept 27, 2004 Online algorithms make a sequence of decisions under uncertainty. One of the most powerful methods of analyzing such problems is by competitive analysis. The competitive ratio of an algorithm is the worst-case ratio of its performance to the performance of the optimal choice, where this optimal is selected with the benefit of hindsight. Competitive Ratio (A) = max (cost of A)/(cost of OPT) This is imprecise and we will elaborate on it further in later lectures. Let's begin with some fun examples: ----------------------------------------------------------------------------------- Rent or Buy Someone has dragged you to go skiing. Renting skis costs R=$50 Buyings skis costs B=$300 Should you rent or buy? That depends on how many times you plan on going skiing. If you have no idea about a probability distribution or anything like that, then a good rule to use might be: Rent the first 5 times and then buy. This has a competitive ratio of 11/6. Case 1) You go skiing at most 5 times. Then your cost is equal to the optimal cost in hindsight, i.e. you made the best decisions. Case 2) You go skiing more than 5 times. Then your cost is 5*50+300=550, because you rented 5 times and then bought. The best thing to do in hindsight would have been to buy the first time, costing only 300. Thus the ratio is 550/300 = 11/6. ----------------------------------------------------------------------------------- Finding a hole in a fence You're standing in front of a long fence. There is a hole somewhere on the fence, but you don't know where it is. Each period, you can take a step left or a step right. Your goal is to find the hole with the fewest number of steps. Knowing nothing about where the hole is, you decide to move as follows. You take a step to the right, the two to the left, four to the right, eight to the left, ... visiting positions 1, -2, 4, -8, 16, ... If the hole is at position n, then it required a minimum of |n| steps to get there from the origin. On the other hand, the cost of this algorithm is: (1+1) + (2+2) + (4+4) + ... (2^m+2^m) + |n| = 2(2^(m+1)-1)+|n| < 2^(m+2)+|n| This is because the cost of going from the origin to position +/-2^i and the returning is 2^i+2^i. How large is 2^m? Well, at most you could have gone twice as far in the wrong direction, so 2^m < 2|n|, and therefore 2^(m+2)+|n| < 8|n|+|n| = 9|n|. Since the optimal cost in hindsight is |n|, the competitive ratio is 9. ----------------------------------------------------------------------------------- List update problem You maintain a list of n items, say, numbered 1,2,...,n. You can think of this as a linked list or as a filing cabinet. There is a sequence of lookups. Each lookup is to a certain item. For the lookup, you must search, one at a time, through the list (cabinet) until you find the requested item. This costs d, where d is the depth of the requested item. Thus one would naturally want to keep the frequently requested items near the front of the list. This suggests the natural Frequency Count Algorithm, which we will analyze next time: Frequency count: Keep items sorted in (reverse) order of how many times they have been looked up. However, one may be able to do even better. For example, if each item is looked up 10 times in a row, then one may want to move the recently requested items to the front of the list, even if they haven't been as requested as others. Here are the rules: 1. A lookup to i costs the depth of i in the list. 2. After the lookup, the requested item may be put anywhere in the list between the start and its position before the lookup. 3. Additional arbitrary swaps of adjacent list elements may be performed at a cost of 1 per swap. Another natural algorithm is the following: Move to front (MTF): Always move the requested item to the front of the list. Claim: Starting with the same initial list, the cost of MTF is at most twice the cost of any other algorithm. Proof: First, let's change rule 2 to rule 2': It is mandatory to move the requested item to the front of the list. Note that this doesn't change the game too much. After all, one can always do arbitrary swaps to move the requested item wherever you want. Moreover, the additional cost of having to move it to the front is not so much. If it was at depth d, it can be returned to depth d with d-1 swaps and anyway, we had to pay d just to find it. Therefore, any algorithm can be implemented with rule 2' and its cost goes up by at most a factor of 2 (because the extra swapping cost is no more than the cost of lookups). Therefore, if we can argue that with rule 2', MTF is optimal, this will mean that MTF is 2-competitive, i.e. its cost is at most twice the cost of any other algorithm on any sequence. Put another way, let cost(A) and cost'(A) be the costs of an algorithm A with rule 2 and rule 2', respectively. Clearly cost(MTF) = cost'(MTF) and from our argument above cost'(A) <= 2 cost(A). Then if we can show cost'(MTF) <= cost'(A) for all A, this would imply that cost(MTF) <= 2 cost(A), which is what we want. Finally, to see that MTF is optimal with rule 2', lets argue that to be optimal, you don't need to do any additional swaps, for any sequence. Let's just argue that we can procrastinate, i.e. delay all swaps until next lookup. Then we can delay them indefinitely. Consider the last swap we were going to do, say swapping a,b to b,a. Let i be the item that is about to be looked up. Case 1. a=i, i.e. we are swapping the next item to be looked up deeper in the list. In this case, we would be better off not swapping it, as swapping it only increased our lookup cost by 1 and, in either case it's going to the front of the list anyway. Case 2. b=i, i.e. we are swapping the next item to be looked up to be earlier in the list. In this case, we are reducing our lookup cost by 1 for the next request, but we are paying 1 to do so. Again, in both cases, the item will be moved to the front of the list. Thus, we could equally as well not do the swap. Case 3. i is not in {a,b}. This swap could be delayed until after the next request, without changing the cost. Thus, all swaps can be delayed and MTF is optimal in the cost' model. ----------------------------------------------------------------------------------- Philosophical discussion It is not clear that optimizing the competitive ratio is always the best thing to do. However, in examples like the above, where you have a simple algorithm with a good competitive ratio, it is a strong argument. Why use anything else when it will be at least as difficult to implement and not more than a factor of 2 faster...