Smoothed Analysis of Algorithms

Smoothed Analysis of Algorithms:
Warum der Simplex Algorithmus normalerweise polynomiell viel Zeit
benötigt


Ich werde in diesem Vortrag den Artikel von Daniel A. Spielman und
Shang-Hua Teng vorstellen, der auf der diesjährigen Konferenz FOCS2001
erscheinen wird.

Smoothed Analysis ist eine neue Methode, die Laufzeit von Programmen zu
untersuchen. Während die Worst-Case-Analyse immer von den ungünstigsten
Umständen ausgeht, (die in der Praxis möglicherweise nie auftreten),
wird bei der Average-Case-Analyse die erwartete Laufzeit bzgl. Aller
möglichen Eingaben einer bestimmten Größe betrachtet. Jedoch hat sich in
den letzten Jahren gezeigt, dass die in der Praxis auftretenden
Instanzen nicht dieselben Eigenschaften haben, wie eine "typische
zufällige" Instanz desselben Problems. "Smoothed Analysis" ist eine
Mischung aus diesen zwei Ansätzen: Für eine gegebene Eingabe x
betrachtet man die erwartete Laufzeit über alle Instanzen, die sich
durch leichte Pertubation von x ergeben. Das Maximum der erwarteten
Laufzeiten über alle möglichen Eingaben x einer bestimmten Größe liefert
die "Smoothed Complexity". Spielmann und Teng zeigen, dass der
Simplex-Algorithmus mit der Schatteneckenregel bzgl. dieser neuen
Komplexität nur polynomiell viel Zeit benötigt. Dies entspricht auch
den Erfahrungen aus der Praxis: Trotz exponentieller Laufzeit im
schlechtesten Fall erfreut sich der Simplex-Algorithmus anhaltender
Beliebtheit, u.a. wegen seiner Schnelligkeit.

Alle InteressentInnen sind zu dem Vortrag herzlich eingeladen.