Ich hab die Vorlesung und die Lösung der Übungen ziemlich stumpf in Anki übertragen und die Karteikarten auswendig gelernt. Übungen während des Semesters auch selber bearbeitet (aber nicht unbedingt alle auf Anhieb verstanden) und die letzte Woche vor der Prüfung die aufgezeichnete Vorlesung angeschaut (aus 2014).

Was ist ein kombinatorisches Optimierungsproblem?

Was versteht man unter relativer Güte (inkl. der weiteren Definitionen der relativen Güte)?

• relative worst-case Güte (p_a^wc)?
• relative Gütegarantie (p_a(n))

Was ist ein Approximationsalgorithmus?

Welche zusätzlichen Bedingungen hatten wir an einen Approximationsalgorithmus gestellt?

• t(n) muss polynomiell sein
• Abschätzung gegen eine optimale Lösung muss möglich sein

Wie ist das TSP definiert?

• die 4 Punkte des kombinatorischen Optimierungsproblems

Wie verhält sich die Max.-Version des TSP zu der Min.-Version?

• Minimierung und Maximierung ist beides gleich schwer (im Gegensatz zur Vertex-Cover / Independent-Set)

Wie ist das TSP-Approximierbar?

• weder mit absoluter noch mit relativer Gütegarantie

Warum ist es nicht mit relativer Gütegarantie approximierbar?

• Beweis mit durch Reduktion mit Hamilton

Wie haben wir TSP dennoch in der Vorlesung approximiert?

• Einschränkung der Eingabe auf Graphen, die die Dreiecksungleichung erfüllen
• Erklärung von Christophides'-Algorithmus inkl. relativer Gütegarantie
• Beweis der relativen Gütegarantie (wurde detailliert so gefragt wie in der VL, als mit c(R*) + wo wird die Dreiecksungleichung verwendet)

Und was tun Sie wenn ich sage, ich kann den besser approximieren?

• Aufzeichnen des Zeugen gegen Christophides inkl. minimaler Spannbaum, leichtestes Matching und Euler-Pfad

Wir haben in der Übung ja noch einen simpleren Algorithmus für die TSP-Approximation behandelt…

• Verdopplung der Kanten des minimalen Spannbaums anstatt leichtestes Matching
• Zeigen des Zeugen aus der Übung inkl. Spannbaum
• Zeigen der relativen Gütegarantie

Weiter zu den Techniken, da haben wir das Max-SAT-Problem behandelt. Wie ist das Max-SAT-Problem definiert?

Welchen Algorithmus haben wir zuerst behandelt um Max-SAT zu approximieren?

• Ein Algorithmus der die Belegungen der x_i würfelt

Welche relative Gütegarantie hat er?

Beweisen Sie die relative Gütegarantie

• Hier wurde detailliert gefragt nach der Indikator-Variable und wie sich daraus aus der Wahrscheinlichkeit der Erwartungswert ergibt

Welche Technik haben wir zu Max-SAT noch kennen gelernt?

• Arithmetisierung von Max-SAT
• Hinschreiben des Integer Linear Programs
• Relaxierung des LPs

Welche relative Güte hatten wir da?

• Nur Hinschreiben hat genügt, kein Beweis dazu (man musste aber wissen, was das k jeweils bedeutet, also einmal eine Schranke für die maximale bzw. minimale Anzahl an Literalen in einer Klausel)

Wie kann man diese beiden Algorithmen kombinieren?

• Algorithmus C_pa der mit WK pa den Algo. A aufruft und mit 1 - pa den Algo. B

Wie haben wir den analysiert?

• pa = 1/2

Welche relative Güte hat er?

• 3/4

Warum is nun C_1/2 besser als die Einzelalgorithmen?

• Wenn man die beiden Funktionen der relativen Güten hinschreibt konvergieren die gegen unterschiedliche Werte
• Die gemeinsame Worst-Case Güte ist 3/4 ⇒ deswegen 3/4 als relative Güte

Hab eine 1.3 bekommen, hab mich ab und zu versprochen und ein paar Details nicht nach Definition gewusst.