====== Approximationsalgorithmen, 2012-07-31 ======

Fragen aus der Prüfung, in Klammern steht teils die Richtung der Antwort:

  * Was ist ein Kombinatorisches Optimierungsproblem?
  * Was ist ein Approximationsalgorithmus? (-> + Unterscheidung: absolute Güte, relative Güte)
  * Erkläre GreedyCol und dessen Güte; Definiere Knotenfärbung
  * Definiere das IndependentSet-Problem; Welchen Zusammenhang gibt es zur Knotenfärbung?
  * Erkläre den GreedyIS-Algorithmus. Unter Verwendung welcher Unbekannten wurde er analysiert? (-> Chromatische Zahl)
  * Es wird nach dem Maximierungsproblem zum Knotenfärbungsproblem gefragt, wie es auf einem Übungsblatt vorkam.
  * Frage nach Randomisierten Algorithmen insb. zu MaxSat, Indikatorvariable, Zusammenhang zwischen Wahrscheinlichkeit der Erfüllung einer Klausel und dem Erwartungswert der Anzahl erfüllter Klauseln.
  * Erkläre Derandomisierung von MaxSat; Was macht ein Problem+Algorithmus derandomisierbar?

Im Allgemeinen schadet es auch nicht, etliche relativen Güteschranken zu den Problemen zu kennen.