Inhalt
In diesem Kapitel sprechen wir über die Möglichkeit Lösungen mit einer Approximationsgarantie zu berechnen.
Termine
- Vorlesung 7 am 08.06.21: Approximation
- Übung 4 am 09.06.21: Greedy_k und Vertex Cover
Veranstaltungen
-
Übung 4
In dieser Übung beschäftigen wir uns mit dem Approximationsalgorithmus Greedyk für das Knapsack-Problem. Außerdem schauen wir uns mit Vertex-Cover noch ein neues Problem an. -
Vorlesung 7
In dieser Vorlesung beginnen wir uns mit Approximationsverfahren zu beschäftigen. Wir lernen dabei den Begriff der Gütegarantie kennen und schauen und einen Approximationsalgorithmus für das Knapsack-Problem an.