Emanuel Schnalzger
6. TopMath-Jahrgang (WS 2009/10)

Mentor: Prof. Dr. Karl Heinz Borgwardt 
Universität Augsburg

BiographieBiographie

Stipendien und Auszeichnungen

• TopMath Presentation Award (2011)
• Max Weber-Programm (seit 04/2010)
• e-fellows.net (seit 12/2009)
• Studienstiftung des deutschen Volkes (seit 03/2009)

ForschungsinteressenForschungsinteressen

Klassisch werden Algorithmen bezüglich ihrer Ausführungszeit im schlimmstmöglichen Fall beurteilt. Das birgt jedoch den Nachteil, dass dabei nicht berücksichtigt wird, wie oft dieser Worst Case in der Praxis auftritt. Beispielsweise ist das Simplexverfahren ein Algorithmus, dessen Ausführungszeit im Worst Case exponentiell (d.h. sehr schlecht) vom Umfang der Eingabedaten abhängt, im praktischen Einsatz jedoch ein äußerst gutes Laufzeitverhalten zeigt.

Genau diese Diskrepanz motiviert sogenannte probabilistische Analysen von Algorithmen hinsichtlich ihrer Ausführungszeit. Zu nennen ist dabei zum einen die Average-Case-Analyse. Unter gewissen stochastischen Annahmen an die Verteilung der Eingabedaten wird dabei eine mittlere Laufzeit auf dem Raum aller möglichen Eingabedaten ermittelt und zur Beurteilung des Algorithmus herangezogen. Zum anderen wurde im Jahr 2001 die sogenannte Smoothed Analysis als eine weitere Möglichkeit, das Laufzeitverhalten von Algorithmen im Anwendungsfall zu untersuchen, vorgeschlagen. Hierbei wird untersucht, wie sich die mittlere Laufzeit des Algorithmus in einer gewissen Umgebung um eine beliebige Eingabe verhält.

Mit diesen Konzepten lässt sich prinzipiell jeder Algorithmus untersuchen. Konkret beschäftige ich mich jedoch mit der Smoothed Analysis von Algorithmen in der Optimierung sowie mit der Fragestellung, ob sich dieses Konzept auch dahingehend erweitern lässt, Eigenschaften von Polyedern zu untersuchen.