FG 413: Algorithmen III (-5)


Für eine Reihe bekannter kominatorischer Optimierungsprobleme, z.B. Graphenfärbung, das Stabile-Menge-Problem in Graphen oder das MAX k-SAT-Problem, sind Nichtapproximierbarkeitsresultate bekannt. Unter gewissen komplexitätstheoretischen Annahmen lassen diese Probleme also keine polynomiellen Algorithmen zu, die auf jeder Instanz eine optimale Lösung bzw. eine gute Approximationslösung berechnen. Daher fragte bereits Karp nach (a) Heuristiken, die auf fast jeder Instanz I eine gute Lösung des Optimierungsproblems bestimmen, und auf jeder Eingabe polynomielle Laufzeit haben, sowie nach (b) Algorithmen mit erwartet polynomieller Laufzeit, die auf jeder Eingabe eine akzeptable Approximationsgüte garantieren und deren erwartete Laufzeit polynomiell ist,
und gab damit den Anstoß zur probabilistischen Analyse von Algorithmen. Im Sinne von Analyse von Algorithmen bei zufälliger Eingabe befassen wir uns in diesem Projekt mit fundamentalen kombinatorischen Problemen wie Graphenfärbung, Finden einer größten stabilen Menge oder dem Erfüllbarkeitsproblem.



Neben der probabilistischen Analyse soll in diesem Projekt der Zufall auch als algorithmisches Konzept studiert werden. Dann lautet die Zielsetzung, durch Randomisierung verbesserte Algorithmen zu entwickeln.


Projektleitung
Schacht, Mathias Prof. Ph. D. (Details) (DFG-Forschergruppen)

Laufzeit
Projektstart: 07/2004
Projektende: 09/2008

Zuletzt aktualisiert 2020-10-03 um 16:44