KIT | KIT-Bibliothek | Impressum | Datenschutz

15: Algorithmen II, Vorlesung, WS 2018/19, 03.12.2018

Sanders, Peter; KIT | Webcast [Hrsg.]

  • 0:00:00 Starten
  • 0:00:05 8 Approximationsalgorithmen
  • 0:00:23 Scheduling unabhängiger gewichteter Jobs auf parallelen Machinen
  • 0:01:03 List Scheduling
  • 0:01:27 Viele Kleine Jobs
  • 0:04:13 Der Approximationsfaktor
  • 0:08:23 Diese Schranke is bestmöglich
  • 0:10:04 Mehr zu Scheduling
  • 0:24:05 Nichtapproximierbarkeit des Handlungsreisendenproblems (TSP)
  • 0:29:53 TSP mit Dreiecksungleichung
  • 0:31:12 2-Approximation durch minimalen Spannbaum
  • 0:35:57 Beispiel
  • 0:40:12 Mehr TSP
  • 0:51:39 Pseudopolynomielle Algorithmen
  • 0:53:41 Beispiel Rucksackproblem
  • 0:55:38 Dynamische Programmierung nach Profit
  • 0:56:59 Fully Polynomial Time Approximation Scheme
  • 1:00:23 FPTAS für Knapsack
  • 1:02:42 Das beste bekannte FPTAS
  • 1:04:31 Fully Polynomial Time Approximation Scheme
  • 1:05:16 Optimale Algorithmen für das Rucksackproblem
  • 1:09:58 9 Fixed-Parameter-Algorithmen
  • 1:11:51 Beispiel: VERTEX COVER (Knotenüberdeckung)
  • 1:13:32 VERTEX COVER Grundlegendes
  • 1:16:02 FIxed parameter tractable
  • 1:19:06 Naive tiefenbeschränkte Suche
  • 1:23:27 Kernbildung für Vertex Cover
Open Access Logo


Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Audio & Video
Publikationsdatum 04.12.2018
Erstellungsdatum 03.12.2018
DOI 10.5445/DIVA/2018-930
Identifikator KITopen-ID: 1000116113
Lizenz KITopen-Lizenz
Serie Algorithmen II, Vorlesung, WS 2018/19
Folge 15
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page