Vorlesung EA/KT mit Schwerpunkt EA,
Sommersem. 2005
Das Skript
Die Semesterstartversion:
Als PS
Als PDF
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!