Pruefung in Approximationsalgorithmen, Juli 2014

  * 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)