Prüfungsstoff für die Vorlesung
"Effiziente Algorithmen II"

Komplexität

• Klassifikation von Entscheidungsproblemen
• Klassifikation von Optimierungsproblemen
• Gütegarantien
• Approximation und NP-Vollständigkeit

• Maschinenbelegung mit unabhängigen Aufgaben
• Maschinenbelegung mit abhängigen Aufgaben
• Knoten-Überdeckungs-Problem
• Bin-Packing-Problem
• Subset-Sum-Problem
• Knapsack-Problem
• Traveling-Salesman-Problem
• Set-Covering-Problem

• Kombinatorische Relaxierungen
• LP-Relaxierungen
• Lagrange-Relaxierungen

• Dynamische Programmierung
• Allgemeine Schnittebenenverfahren
• Branch-and-Bound
• Branch-and-Cut
• Simulated Annealing

• Berechnung linearer Beschreibungen
• Allgemeine Resultate und Liftungssätze

• Anwendung: Via-Minimierung
• Heuristiken für das Max-Cut-Problem
• Das Cut-Polytop
• Separierung für das Cut-Polytop