13: Algorithmen II, Vorlesung, WS 2019/20, 25.11.2019
Sanders, Peter
; Lamm, Sebastian
; Heuer, Tobias
; Zentrum für Mediales Lernen (ZML) [Hrsg.]
; Lamm, Sebastian
; Heuer, Tobias
; Zentrum für Mediales Lernen (ZML) [Hrsg.]- 0:00:00 Start
- 0:00:50 Approximationsalgorithmen
- 0:06:54 Scheduling unabhängiger gewichteter Jobs auf parallelen Maschinen
- 0:10:22 List Scheduling
- 0:19:27 Der Approximationsfaktor
- 0:34:27 Nichtapproximierbarkeit des Handlungsreisendenproblems (TSP)
- 0:37:04 Beweis
- 0:45:57 Euler-Touren/-Kreise
- 0:48:36 2-Approximation durch minimalen Spannbaum
- 0:51:56 Beispiel
- 0:54:47 Beweis
- 0:55:39 Zusatz: Mehr TSP
- 1:07:03 Pseudopolynomielle Algorithmen
- 1:09:07 Beispiel: Rucksackproblem
- 1:10:50 Dynamische Programmierung nach Profit
- 1:14:45 Fully Polynomial Time Approximation Scheme
- 1:16:27 Beispielschranken
- 1:18:17 FPTAS für Knapsack
| Zugehörige Institution(en) am KIT | Institut für Theoretische Informatik (ITI) |
| Publikationstyp | Audio & Video |
| Publikationsdatum | 26.11.2019 |
| Erstellungsdatum | 25.11.2019 |
| Sprache | Deutsch |
| DOI | 10.5445/DIVA/2019-918 |
| Identifikator | KITopen-ID: 1000117074 |
| Lizenz | KITopen-Lizenz |
| Serie | Algorithmen II, Vorlesung, WS 2019/20 |
| Folge | 13 |