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.