Was ist ein kombinatorisches Optimierungsproblem? (→ 4-Tupel, die Komponenten nennen)
Welche Anforderungen an Approximationsalgorithmen werden gestellt? (→polynomielle Laufzeit, beweisbare Guete)
Die ganzen Definitionen zu relativer Guete (individuelle relative Guete, relative worst-case Guete, …)
Definition von TSP und metrischem TSP angeben (das Tupel)
Christophides Algorithmus, erst alle 5 Schritte, dann die Analyse zu jedem einzelnen Schritt und damit die Guete herleiten? (→ \rho ⇐ 3/2-1/n), dabei auch kleinere Zwischenfragen wie: wann kann man eine Eulertour berechnen? Was ist ein leichtestes Matching?
Wo benutzt der Dreiecksungleichung (→ nirgends, nur fuer die Analyse braucht man sie an zwei Stellen)
geht das auch besser? (→ nein, gibt entsprechenden Zeugen, den muss man auch beschreiben koennen!)
MaxSAT Problem definieren
Wie funktioniert Algorithmus A? Was ist sein Erwartungswert? (→ Wahrscheinlichkeit fuer Erfuellung einer Klausel, Indikatorvariable einfuehren, entsprechende Summe fuer Erwartungswert bilden)
Wie kann man das deterministisch machen? (→ Derandomisierung erklaeren, erklaeren warum der Algorithmus keine „schlechteren“ Erwartungswerte finden kann)