Kapitel 4 – Approximation

Inhalt

In diesem Kapitel sprechen wir über die Möglichkeit Lösungen mit einer Approximationsgarantie zu berechnen.

Veranstaltungen

  • Übung 5
    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.