15-451 Algorithms Spring 2004 April 6, 2004 Danny Sleator Competitive analysis of Online Algorithms - rent or buy? - competitive algorithms - the list update problem - the migration problem ========================================================================== (Some of the material from Avrim Blum) On-line algorithms ================== Any situation in which you have to make a decision on the fly without knowing the future. Examples include: controlling an elevator data structures (search list, self-adjusting trees) scheduling problems (processor scheduling) caching "Competitive Analysis" is an approch to analyzing these problems. (Define more precisely later, first a simple example) Rent-or-buy? ============ Simple online problem called the rent-or-buy problem, aka the tuxedo-rental problem. Say you get invited to some formal event and need to wear a tuxedo. Can either rent for $50 or buy for $300. So, you decide to rent. Then get invited to one again. Pretty soon, if you get invited to more than 6, you're wishing you had bought right at the start. Optimal strategy is: if you know you will be invited to more than 6 before the styles or your waistline changes then you should buy. Otherwise you should rent. But, what if you don't know? To talk about goodness of an online algorithm, we're going to look at the Competitive Ratio measure. Competitive ratio (CR) is worst case (maximum) over sequences of events of the ratio: (our cost)/OPT, where OPT = optimal cost in hindsight. "cost" means total cost over all time. In this case, what is CR of algorithm that says "buy right away"? Worst case is: only go once. Ratio is 300/50 = 6. What about algorithm that says "Rent forever"? Worst case is: keep getting invited. Ratio is infinite. Here's an algorithm with a competitive ratio of (2 - r/p), where r = rent cost and p = purchase cost (and r <= p): "Rent so long as total spent is less than purchase cost, then buy". (e.g., here it is "rent 5 times then buy") [Could be called the "better late than never" strategy.] If you needed a tux 5 or fewer times you were optimal. If you needed it 6 times, you spent $250 + $300 = $550, but optimal was $300. If you needed it > 6 times, you spent $550 but optimal was $300. We pay either OPT (when OPT < p) or 2*OPT-r (when OPT = p), so our ratio is (2 - r/p). Claim: Can't beat ratio of (2 - r/p) with a deterministic alg. Proof: what if the time you buy is the last time you ever use it. Say you rented k times. You paid k*rent + purchase. In hindsight, OPT = min(purchase, (k+1)*rent). So, ratio = [kr + p]/[min(p, (k+1)r)] = [(k+1)r + p - r]/[min(p, (k+1)r)] case 1: p <= (k+1)r. Then, ratio >= [2p-r]/p = (2 - r/p). case 2: (k+1)r <= p. Then, ratio >= 1 + (p-r)/[(k+1)r] >= 1 + (p-r)/p = 2 - r/p. Competitive algorithms ====================== An algorithm A is c-competitive if there exists a number a such that for any B and sigma: C_A(sigma) <= c C_B(sigma) + a. Where sigma is a sequence of requests, and C_A(sigma) is the cost of algorithm A on sequence sigma. Eventually we'll make use of the extension of this definition to handle randomized on-line algorithms. In this case C_A(sigma) is the expected cost of algorithm A on sequence sigma, and the expectation is taken over all of A's random choices. Competitive analysis has been used to design and analyze many important algorithms in data structures, computer systems, and networks. The List Update Problem ======================= Groundrules for the problem: There's a list of n items. (For simplicity we fix n). The positions in the list are numbered 1, 2, ... n. Position 1 is the front of the list. An item x can be accessed. The operation is called Access(x). The cost of the operation is the position i of x in the list. After doing an access, the algorithm is allowed to rearrange the list by doing swaps of adjacent elements. The cost of a swap is 1. So an on-line algorithm is specified by describing which swaps are done after an element is accessed. (Without loss of generality we can give off-line optimum algorithm the power to do its sawps any time it wants, and not associate them with any particular access.) The goal is to devise and analyze an on-line algorithm for doing Access() with a small competitive factor. Here are several algorithms to consider. Single Exhchange: After accessing x, if x is not at the front of the list, swap it with its neighbor toward the front. Frequency Count: Maintain a frequence of access for each item. Keep the list ordered by non-increasing frequency from fron to back. Move To Front (MTF): After an access to an element x, do a series of swaps to move x to the front of the list. It's easy to construct sample sequences to show that Single Exchange and Frequency Count have competitive factors that are Omega(n). Theorem: MTF is a 4-competitive algorithm for the list-update problem. Proof: We'll use the potential function method. There will be a potential function that depends on the state of the MTF algorithm and the state of the "opponent" algorithm B, which can be any algorithm, even one which can see the future. Using this potential, we'll show that the amortized cost to MTF of an access is at most 4 times the cost of that access to B. Here are the two lists: _ _ _ _ _ _ _ _ _ B |_|_|_|_|_|_|_|_|...|_| _ _ _ _ _ _ _ _ _ MTF |_|_|_|_|_|_|_|_|...|_| Phi = 2*(The number of inversions between B's list and MTF's list) Recall that an inversion is a pair of distinct elements (x,y) that appear in one order in B's list and in a different order in MTF's list. It's a measure of the similarity of the lists. Using this potential, we'll analyze the amortized cost to MTF of Access(x), and the amortized cost to MTF that is incurred when B does a swap. (Note that in this case MTF incurrs zero cost, but it will have a non-zero amortized cost. To be complete the analysis must take this into account.). In each case we'll show that the amortized cost to MTF is at most 4 times the cost to B. That is, we'll show: AC <= 4C MTF B We can then sum the amortized costs, and add in the initial potential minus the final potential to bound the actual cost of the entire sequence of accesses to MTF. Analysis of Access(x) --------------------- _____________ B |_____x_______| _____________ MTF |_________x___| Define sets S = {y | y is before x in MTF and y is before x in B} T = {y | y is before x in MTF and y is after x in B} What is the cost of the access to MTF in terms of these sets? C = 1 + |S| + |T| + |S| + |T| = 1+2(|S|+|T|) MTF \___________/ \_________/ find cost swap cost C >= |S| + 1 Because all of S is before x in B. B What happens to the potential as a result of this operation? Well, here's MTF after the operation: _____________ MTF |x____________| The only changes in the inversions involve element x, because all other pairs stay in the same relative order. We can write the change in Phi precisely: Delta(Phi) = 2 (|S| - |T|) Because for every element of S the the number of inversions increases by 1 and for every element of T the number of inversions decreases by 1. Using this we can evaluate the amortized cost of the access to MTF. AC = 2 (|S| - |T|) 1+2(|S|+|T|) = 1+4|S| <= 4(1+|S|) <= 4 C MTF B This completes the amortized analysis of Access(x). Analysis of B swapping ---------------------- C = 0 C = 1 MTF B Delta(Phi) <= 2 AC <= 2 C <= 4 C MTF B B Putting the parts together -------------------------- Summing the amortized costs we get: Total Cost to MTF <= 4*(Total Cost to B) + Phi(init) - Phi(final) Phi(init) - Phi(final) <= n choose 2 = n(n-1)/2 Total Cost to MTF <= 4*(Total Cost to B) + (n choose 2) And the (n choose 2) term is actually 0 if MTF's list and B's list start out the same. QED. Migration ========= This is a generalization of the paging problem. It takes place on an undirected graph with edge lengths. (Each node represents a processor, and the edge lengths represent the latency in the network.) A page is to be kept in one of the processors. There is a sequence of accesses to the page from the nodes. The cost of an access = dist from request to page. Also, the page may be moved at a cost of pd (p is a fixed constant -- the page size, and d is the distance to move the page.) Problem: Decide on-line where to keep the page. For simplicity at first we consider just a graph with two nodes, 1 and 2, and an edge between them. Counting algorithm: Maintain a count on each node (initially 0). Call them c1 and c2. Four cases: Page in 1, access to 1: Do nothing Page in 1, access to 2: c2++ if c2 = 2p then migrate from 1 to 2, and c2 <-- 0. (Other 2 cases symmetric) Theorem: The counting algorithm is 3-competitive, which is optimal. Proof: see slides.