In diesem Modul werden wir verschiedene Näherungsalgorithmen für das Problem des Lastausgleichs untersuchen. Bei diesem Problem geht es darum, eine gegebene Menge von Aufträgen, die jeweils eine bestimmte Bearbeitungszeit haben, auf eine Reihe von Rechnern zu verteilen. Das Ziel ist es, dies so zu tun, dass alle Aufträge so schnell wie möglich erledigt werden. Wir werden die Qualität der berechneten Lösungen anhand des Konzepts der rho-Approximation analysieren, das wir in der vorherigen Vorlesung kennengelernt haben. Bei dieser Analyse werden wir sehen, dass untere Schranken für die optimale Lösung eine entscheidende Rolle bei der Analyse spielen (oder, bei Maximierungsproblemen: obere Schranken).

In diesem Modul führen wir die Technik der LP-Relaxation ein, um Approximationsalgorithmen zu entwerfen, und erklären, wie man das Approximationsverhältnis eines auf LP-Relaxation basierenden Algorithmus analysiert. Wir werden dies am Beispiel des (gewichteten) Vertex Cover Problems tun. Bevor wir jedoch die Technik der LP-Relaxation erklären, geben wir zunächst einen einfachen 2-Approximationsalgorithmus für das ungewichtete Vertex-Cover-Problem an.

In diesem Modul stellen wir das Konzept der Polynomial-Time Approximation Scheme (PTAS) vor. Dabei handelt es sich um Algorithmen, die einer optimalen Lösung beliebig nahe kommen können. Wir beschreiben eine allgemeine Technik zum Entwurf von PTAS und wenden sie auf das berühmte Knapsack-Problem an. Schließlich werden wir sehen, wie PTAS, die mit der allgemeinen Technik entworfen wurden, analysiert werden können.