Vorlesung EA/KT mit Schwerpunkt EA, Sommersem. 2005

Das Skript

Die semesterbegleitend überarbeitete Version (aka "The Director's Cut") (30.03.2007): Als PS    Als PDF
Geändert gegenüber der Startversion:

• Bei der Kontraktion von Mincut die Operation einheitlich auf gewichteten Graphen statt auf Multigraphen definiert. Dies führt dazu, dass in Kapitel 5.5 auch noch ein bisschen geändert werden muss.
• Bei Vertex Cover den "Kammgraphen" als Beispiel hinzugefügt.
• Den alternativen Beweis zur Güte (1+ln n) bei Set Cover "eingehängt."
• Den Beweis für das FPTAS beim Rucksackproblem ein wenig kürzer gemacht.
• Den Beweis für das PTAS beim Makespan Scheduling ein wenig vereinfacht.
• Anhang zu Schubfachprinzip hinzugefügt.
• Anhang eine bessere Abschätzung einer Rekursionsgleichung hinzugefügt.
• Sperrflussberechnung in O(n*n): Definition von pot(v) für den Fall v Quelle oder v Senke ergänzt.
• Beim Lemma, das die nicht-saturierenden Push-Operationen zählt, eine andere Potenzialfunktion verwendet, die zu besserer Abschätzung (Konstante 4 statt 8) führt. Analyse funktioniert aber fast genauso wie die alte.
• Einige kleine Tippfehler beseitigt.

Kommentare und Verbesserungsvorschläge erwünscht!