KIT | KIT-Bibliothek | Impressum | Datenschutz

10: Theoretische Grundlagen der Informatik, Vorlesung, WS 2018/19, 11.12.2018

Ueckerdt, Torsten; KIT | Webcast [Hrsg.]

  • 0:00:00 Start
  • 0:01:01 Verallgemeinerte NP-Schwere
  • 0:03:38 Das Problem INTEGER PROGRAMMING
  • 0:07:18 INTEGER PROGRAMMING ist NP-schwer
  • 0:15:12 Bemerkungen
  • 0:23:00 Pseudopolynomiale Algorithmen
  • 0:33:54 Starke NP-Vollständigkeit
  • 0:40:34 Absolute Approximationsalgorithmen
  • 0:44:01 Das allgemeine KNAPSACK-Suchproblem
  • 0:47:08 Negativ-Resultat
  • 0:50:24 (Kontrapositions-)Beweis
  • 0:55:47 Approximation mit relativer Gütegarantie
  • 0:57:13 Genereller Ansatz
  • 1:06:09 Grenzen für den Greedy-Algorithmus


Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Audio & Video
Publikationsdatum 13.12.2018
Erstellungsdatum 11.12.2018
DOI 10.5445/DIVA/2018-965
Identifikator KITopen-ID: 1000116148
Serie Theoretische Grundlagen der Informatik, Vorlesung, WS 2018/19
Lizenz KITopen-Lizenz
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page