KIT | KIT-Bibliothek | Impressum | Datenschutz

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

Sanders, Peter; Lamm, Sebastian; Heuer, Tobias; Zentrum für Mediales Lernen (ZML) [Hrsg.]

  • 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


Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Audio & Video
Publikationsdatum 13.01.2020
Erstellungsdatum 07.01.2020
DOI 10.5445/DIVA/2020-12
Identifikator KITopen-ID: 1000117180
Serie Algorithmen II, Vorlesung, WS 2019/20
Lizenz KITopen-Lizenz
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page