• Einführung
• Lineares Programmieren: Definition und Varianten
• Lineares Programmieren: Grundlegende Konzepte

• Simplex-Algorithmus

• Abschluss Simplex Algorithmus
• Bitkomplexität von arithmetischen Algorithmen
• Cramersche Regel

• Ellipsoid-Algorithmus

• LP-Dualität: Motivation und Beispiel
• schwache Dualität

• Fourier-Motzkin Elimination
• Farkas-Lemma

• Beweis Farkas Lemma
• starke Dualität

• Nullsummenspiele
• Von Neumanns Minimax-Theorem: Beweis durch LP-Dualität

• Median-Algorithmus von Floyd-Rivest: Funktionsweise

• Medianalgorithmus von Floyd-Rivest: Analyse

• KKT-Algorithmus zum Finden des MST: Funktionsweise und Korrektheit

• KKT-Algorithmus zum Finden des MST: erwartete Laufzeit mit Rückwärtsanalyse

KKT-Algorithmus für MST: Analyse

• Random-Walk Algorithmus für MAX2-SAT

• Nächste-Nachbar Suche in hohen Dimensionen: Definition und Beispiele

• Nächste Nachbar Suche in hohen Dimensionen: Reduktion auf nahe Nachbar Suche

• Lösung des naher Nachbar Problems mit Locality Sensitive Hashing
• Beispiele für LSH-Familien

• Parametrisierte Algorithmen: Motivation
• Parametrisierter Algorithmus für Vertex Cover

• Baumweite: Definition und Eigenschaften

• Baumweite: Algorithmische Anwendung für Maximum Independent Set

• Approximationsalgorithmen: VERTEX-COVER und SET-COVER

• Inapproximierbarkeit von allgemeinem TSP

Metrisches TSP: Baumheuristig und Christofides Heuristik

Aroras PTAS für euklidisches TSP: schöne Eingaben, Quadbäume und Portale

• Aroras PTAS für euklidisches TSP: portalbeachtende Touren, es gibt ebene portalbeachtende Touren, die jedes Portal höchstens zweimal benutzen

• Aroras PTAS: finden einer kürzesten portalbeachtenden Tour mit dynamischer Programmierung, eine kürzeste portalbeachtende Tour approximiert eine kürzestes Tour