• Administrativa
• Einleitung
• Vertex Cover: NP-Vollständigkeit

• Vertex Cover: 2-Approximation durch maximales Matching
• Set Cover: O(ln n)-Approximation durch einen gierigen Algorithmus

• Grundlegende Definitionen: kombinatorisches Optimierungsproblem, Approximationsalgorithmus, Approximationsgüte
• Weitere einfache gierige Approximationsalgorithmen: (2-2/k)-Approximation für Multiway Cut

• gierige Approximationsalgorithmen: k-center
• Approximation durch lokale Suche: Minimum Degree Spanning Tree

• Analyse der lokalen Suche für Minimum Degree Spanning Tree
  

• Definitionen PTAS und FPTAS
  
• FPTAS für das Rucksackproblem
  
• 2-Approximation für Bin Packing
  

• Hardness of Approximation für Bin-Packing: Wenn ein (3/2 - eps)-Approximationsalgorithmis für Bin-Packing existiert, dann ist P=NP.
• APTAS für Bin-Packing

• APTAS für Bin-Packing
• Entscheidungsprobleme mit Parameter, Zahlprobleme, pseudopolynomielle Algorithmen und starke NP-vollständigkeit

• starke NP-vollständigkeit und Existenz von PTASsen
• einfache randomisierte Approximationsalgorithmen: MAX-SAT

TSP

• Nichtapproximierbarkeit von TSP mit allgemeinen Abstandsfunktionen
• MST-Heuristik und Christofides-Heuristik für metrisches TSP

Aroras PTAS für euklidisches TSP

Aroras PTAS für euklidisches TSP

Aroras PTAS für euklidisches TSP

• Definitionen und Begriffe Lineares Programmieren
  
• ILP-Formulierung von Vertex Cover
  
• LP-Relaxierung
  
• LP-Rounding
  

Der Algorithmus von Karmarkar und Karp für das Bin-Packing Problem

• Konfigurations-LP: Definition und Lösbarkeit
• Harmonisches Gruppieren

Karmarkar-Karp

• Harmonisches Gruppieren: Eigenschaften
• Eigenschaften der gerundeten Lösung

Karmarkar-Karp

• Rekursives Runden des LPs
• Abschluss

Probabilistisches Runden von LPs

• LP-Relaxierung von SET COVER

Probabilistisches Runden von LPs

• Runden der LP-Relaxierung von SET-COVER
• Erhöhung der Wahrscheinlichkeit, eine zulässige Lösung für das LP zu erhalten durch wiederholtes Würfeln

LPs und Integrality Gaps

• Integrality Gap Konstruktion für Set Cover mit Hilfe von linearer Algebra

Integrality Gap des Set Cover LPs

• Abschluss

Probabilistisches Runden II

• MAX-SAT: (1- 1/e)-Approximation durch Runden eines LPs

Probabilistisches Runden II - MAX-SAT

• (1- 1/e)-Approximation durch Runden eines LPs
• 3/4-Approximation durch nicht-lineares Rundes eines LPs

Dualität von LPs

• duales LP: Motivation und Definition
• schwache Dualität
• starke Dualität

Dual Fitting Analyse des gierigen Algorithmus für SET COVER

Dual Fitting Analyse des gierigen Algorithms für eingeschränktes SET MULTICOVER

Primal-Dual Algorithmen: SET COVER und FEEDBACK VERTEX SET

Primal Dual Approximation für FEEDBACK VERTEX SET

Max Cut und Semidefinite Programmierung

Die MAX-CUT Approximation von Goemans-Williamson

Approximationshärte

• Definition Gap-erzeugende Reduktion
• Nichtapproximierbarkeit des Kanten-disjunkten Pfad Problems

Approximationshärte

• Beweis, dass MAX-3-SAT keinen PTAS besitzt