Education
22 | 0:00:00 Starten 0:00:42 13 Onlinealgorithmen 0:05:35 Examples 0:08:09 Competitive analysis 0:09:19 A typical online problem: ski rental 0:11:31 Upper bound for ski rental 0:14:33 Lower bound for ski rental 0:18:07 Paging 0:20:16 Definitions 0:21:49 Paging algorithms 0:25:11 Longest Forward Distance is optimal 0:27:34 Using the claim 0:29:01 Proof the claim 0:29:44 Comparison of algorithms 0:34:33 A general lower bound 0:38:53 Resource augmentation 0:40:14 Conservative algorithms 0:43:26 Competitive ratio 0:46:50 Counting the faults of OPT 0:47:32 Conclusion 0:48:30 Competitive analysis 0:49:57 Notes 0:51:02 New results 0:54:25 Randomized algorithms 0:55:38 Three types of adversaries 1:00:46 Markig Algorithm 1:04:28 Analysis of REMARk 1:06:21 Lower bound for OPT 1:07:42 Discussion 1:08:50 Why competitive analysis? 1:16:24 Disadvantages of competetive analysis