Algorithmen II, Vorlesung, WS 2016/17, 18.01.2017, 22
Sanders, Peter
; KIT | Webcast [Hrsg.]
; KIT | Webcast [Hrsg.]- 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
| Zugehörige Institution(en) am KIT | Institut für Theoretische Informatik (ITI) |
| Publikationstyp | Audio & Video |
| Publikationsdatum | 20.01.2017 |
| Erstellungsdatum | 18.01.2017 |
| Sprache | Deutsch |
| DOI | 10.5445/DIVA/2017-49 |
| Identifikator | KITopen-ID: 1000114463 |
| Lizenz | KITopen-Lizenz |
| Serie | Algorithmen II, Vorlesung, WS 2016/17 |
| Folge | 22 |