12: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 10.12.2019
- 0:00:00 Start
- 0:00:42 Wiederholung letzte Vorlesung
- 0:08:12 Definition
- 0:14:31 Metrisches TSP
- 0:16:07 Approximation von min-METRIC-TSP
- 0:27:08 Bemerkungen zur Approximierbarkeit
- 0:31:25 Approximationsschemata
- 0:37:51 Ein FPTAS für max-KNAPSACK
- 0:42:18 Pseudopolynomialer. optimaler Algorithmus für max-KNAPSACK
- 0:52:46 Maximierungsprobleme
- 1:01:47 Optimierungsprobleme
- 1:10:58 Approximierbarkeit von min-Vertex-Color
- 1:23:39 Abschluss des Kapitels zur Komplexitätstheorie
| Zugehörige Institution(en) am KIT | Institut für Theoretische Informatik (ITI) |
| Publikationstyp | Audio & Video |
| Publikationsdatum | 12.12.2019 |
| Erstellungsdatum | 10.12.2019 |
| Sprache | Deutsch |
| DOI | 10.5445/DIVA/2019-974 |
| Identifikator | KITopen-ID: 1000117125 |
| Lizenz | KITopen-Lizenz |
| Serie | Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20 |
| Folge | 12 |