Eine Vielzahl von kombinatorischen Optimierungsproblemen lässt sich mit Hilfe von Graphen modellieren. Die daraus hervorgehenden Fragestellungen wie beispielsweise das Steinerbaumproblem oder Graphenfärbungsprobleme sind jedoch oft NP-schwer und können daher nicht effizient gelöst werden.
Dennoch treten diese Probleme in vielen Anwendungen auf und müssen algorithmisch behandelt werden. Unsere Gruppe untersucht die folgenden Lösungsansätze:
- Approximationsalgorithmen.
- Diese liefern eine approximative (näherungsweise) Lösung zusammen mit einer Garantie für die Abweichung der gefundenen Lösung vom theoretischen Optimum.
- Randomisierte Algorithmen.
- Für viele Probleme kennt man Algorithmen, die in bestimmten Situationen Entscheidungen zufällig treffen und dadurch mit (nachweislich) hoher Wahrscheinlichkeit eine gute Lösung finden. Randomisierte Algorithmen sind oft auch aufgrund ihrer Einfachheit und geringeren Laufzeit gegenüber deterministischen Algorithmen von Vorteil.
- Probabilistische Analyse von Algorithmen.
- Hierbei geht es darum, für einen bestimmten Algorithmus nachzuweisen, dass er auf fast allen Instanzen des Problems (die gemäß einer bestimmten Verteilung zufällig auftreten) eine gute Lösung findet.
Ergänzend hierzu befassen wir uns auch mit der Frage der Nichtapproximierbarkeit von Problemen, d.h. dem Nachweis, dass ein bestimmtes Problem (unter gegebenen komplexitätstheoretischen Annahmen) nicht nur schwer exakt zu lösen ist, sondern sogar (bis auf einen bestimmten Faktor) nicht approximiert werden kann.
English