Page 1 Princeton University â€¢ COS 423 â€¢ Theory of Algorithms â€¢ Spring 2001 â€¢ Kevin Wayne Competitive Analysis 2 Beyond Worst Case Analysis Worst-case analysis. ¦ Analyze running time as function of worst input of a given size. Average case analysis. ¦ Analyze average running time over some distribution of inputs. ¦ Ex: quicksort. Amortized analysis. ¦ Worst-case bound on sequence of operations. ¦ Ex: splay trees, union-find. Competitive analysis. ¦ Make quantitative statements about online algorithms. ¦ Ex: paging, load balancing. 3 Online Algorithm and Competitive Analysis Paging problem: Given two-level store consisting of fast memory (cache) that can hold k pages, and slow memory that can store infinitely many pages. ¦ Sequence of page requests p: â€“ if page p already in cache, no cost incurred â€“ otherwise, eject some other page q from cache and replace with p, and pay unit cost for page fault. ¦ If p not in cache, which page q should you evict? ¦ Most fundamental and practically important online problem in CS. 4 Online Algorithm and Competitive Analysis Competitive analysis. (Sleator-Tarjan) ¦ Algorithm A is r -competitive if there exists some constant b such that for every sequence of inputs s : where OPT is optimal offline algorithm. ¦ OPT = MIN: evict page whose next access is furthest away. ¦ A = LRU: evict page whose most recent access was earliest ! Traditional analysis completely uninformative. ! We show LRU is k-competitive. ¦ A = LIFO: evict page brought in most recently. ! LIFO can have arbitrarily bad competitive ratio. ¦ Fact: no online paging algorithm is better than k-competitive. . ) ( cost ) ( cost b OPT A + £ s r s Page 2 Princeton University â€¢ COS 423 â€¢ Theory of Algorithms â€¢ Spring 2001 â€¢ Kevin Wayne Competitive Analysis 2 Beyond Worst Case Analysis Worst-case analysis. ¦ Analyze running time as function of worst input of a given size. Average case analysis. ¦ Analyze average running time over some distribution of inputs. ¦ Ex: quicksort. Amortized analysis. ¦ Worst-case bound on sequence of operations. ¦ Ex: splay trees, union-find. Competitive analysis. ¦ Make quantitative statements about online algorithms. ¦ Ex: paging, load balancing. 3 Online Algorithm and Competitive Analysis Paging problem: Given two-level store consisting of fast memory (cache) that can hold k pages, and slow memory that can store infinitely many pages. ¦ Sequence of page requests p: â€“ if page p already in cache, no cost incurred â€“ otherwise, eject some other page q from cache and replace with p, and pay unit cost for page fault. ¦ If p not in cache, which page q should you evict? ¦ Most fundamental and practically important online problem in CS. 4 Online Algorithm and Competitive Analysis Competitive analysis. (Sleator-Tarjan) ¦ Algorithm A is r -competitive if there exists some constant b such that for every sequence of inputs s : where OPT is optimal offline algorithm. ¦ OPT = MIN: evict page whose next access is furthest away. ¦ A = LRU: evict page whose most recent access was earliest ! Traditional analysis completely uninformative. ! We show LRU is k-competitive. ¦ A = LIFO: evict page brought in most recently. ! LIFO can have arbitrarily bad competitive ratio. ¦ Fact: no online paging algorithm is better than k-competitive. . ) ( cost ) ( cost b OPT A + £ s r s 5 Online Algorithm and Competitive Analysis Theorem. LRU is k-competitive. Proof: Let t be a subsequence of s on which LRU faults exactly k times, and t does not contain fist access in s . Let p denote page requested just before t . ¦ Case 1: LRU faults in sequence t on p. â€“ t requests at least k+1 different pages MIN faults at least once ¦ Case 2: LRU faults on some page, say q, at least twice in t . â€“ t requests at least k+1 different pages MIN faults at least once 6 Online Algorithm and Competitive Analysis Theorem. LRU is k-competitive. Proof: Let t be a subsequence of s on which LRU faults exactly k times, and t does not contain fist access in s . Let p denote page requested just before t . ¦ Case 3: LRU does not fault on p, nor on any page more than once. â€“ k different pages are accessed and faulted on, none of which is p â€“ p is in MINâ€™s cache at start of t MIN faults at least once s 0 s 1 s 2 . . . s 1 s p . . . s : LRU faults k times MIN faults â€¡ 1 times LRU faults £ k timesRead More