Parametrisierte Algorithmen (SS 2003)

Peter Rossmanith

Sprechstunde: Mittwochs 11-12 Uhr

Bereich

2+2 SWS Vorlesung im Bereich Theoretische Informatik

Zeit und Ort

Vorlesung Dienstags 10-12 Uhr c.t. im Seminarraum 4013
Übung Donnerstags 10-12 Uhr c.t. im Seminarraum 6103.

Folien

Vorraussetzungen

Vordiplom.

Literatur

Es gibt bislang nur ein Buch zu diesem Thema:
R. G. Downey and M. R. Fellows. Parameterized Complexity. Springer-Verlag, 1999.
Dieses Buch liegt im Semesterapparat in der Informatikbibliothek aus.

Die Vorlesungsfolien werden im Netz zur Verfügung gestellt.

Inhalt

Viele Probleme, die in der Praxis auftauchen, sind NP-hart und werden daher von Theoretikern in der klassischen Sichtweise als praktisch nicht exakt lösbar eingestuft. Natürlich müssen die Probleme praktisch doch gelöst werden, wobei Approximationsalgorithmen oder Heuristiken verwendet werden können. Bei vielen praktischen Problemen werden dabei erstaunlich gute Ergebnisse in kurzer Zeit erzielt. Es scheint als seien praktisch auftretende Probleminstanzen nicht so hart und die NP-Vollständigkeit manifestiert sich in künstlichen, praxisfernen Instanzen.

Parametrisierte Algorithmen versuchen gezielt die Einfachheit praktisch vorkommender Probleminstanzen auszunutzen. Um diese ''Einfachheit'' erfassen zu können, wird ein Parameter verwendet, der oft k genannt wird. Die Probleminstanz wird als einfach angesehen, wenn der Parameter klein ist. Ein Beispiel ist das Auflösen von Konflikten in Konfliktgraphen. Dieser Graph gibt an, welche Messergebnisse zueinander in Widerspruch stehen. Man möchte nun möglichst wenige Messergebnisse ignorieren, so dass keine Konflikte verbleiben. Dieses Problem ist NP-vollständig. Wenn wir die Anzahl der Konflikte mit k bezeichnen, können wir aber einen einfachen Algorithmus finden, dessen Laufzeit eine Funktion von k multipliziert mit einem Polynom der Grösse des Graphen ist. In der Praxis ist aber k sehr klein, da nur wenige Messfehler vorkommen. Der resultierende Algorithmus gibt ein garantiert optimales Ergebnis.

In dieser Vorlesung werden solche parametrisierten Algorithmen und allgemeine Techniken, solche Algorithmen zu entwerfen, vorgestellt. Der Schwerpunkt liegt dabei auf jenen Techniken, die praktisch verwertbare Algorithmen hervorbringen. Daneben gibt es auch Verfahren, um nur zu zeigen, daß ein Problem einen parametrisierten Algorithmus besitzt, ohne zunächst auf die Effizienz zu achten. Schließlich gibt es noch Methoden, die nachweisen, daß ein Problem wahrscheinlich auch parametrisiert nicht schnell gelöst werden kann.