13 |

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