20: Algorithmen II, Vorlesung, WS 2019/20, 07.01.2020

20 | 0:00:00 Start 0:01:25 Onlinealgorithmen 0:05:59 Competitive analysis 0:07:29 A typical online problem: ski rental 0:08:55 Upper bound for ski rental 0:10:55 Lower bound for ski rental 0:16:04 Paging 0:19:44 Definitions 0:20:23 Paging algorithms 0:24:41 Longest Forward Distance 0:27:48 Using the claim 0:29:48 Comparison of algorithms 0:35:28 A general lower bound 0:41:28 Resource augmentation 0:42:53 Conservative algorithms 0:44:42 Competitive ratio 0:47:01 Counting the faults of OPT 0:48:57 Conclusion 0:50:17 Notes 0:53:07 New results 0:54:51 Randomized algorithms 0:56:49 Three types of adversaries 0:59:04 Marking Algorithms 1:02:31 Competitive ratio of RMARK 1:03:33 Analysis of RMARK 1:08:00 Lower bound for OPT 1:09:59 Upper bound for RMARK 1:10:51 Discussion 1:15:54 Disadvantages of competitive analysis 1:16:55 Stringology