Prof. Dr. Heiko Röglin erhält ERC Starting Grant

Der Europäische Forschungsrat (ERC) hat einen ERC Starting Grant für
Professor Röglin bewilligt. In dem Projekt "Algorithms beyond the Worst
Case", das vom ERC in den nächsten fünf Jahren mit insgesamt 1,23
Millionen Euro gefördert wird, soll die vorherrschende Diskrepanz
zwischen der theoretischen Analyse und der experimentellen Evaluation
von Algorithmen verkleinert werden.

Viele Algorithmen, die in Experimenten und praktischen Anwendungen
hervorragende Ergebnisse erzielen, sind aus theoretischer Sicht
schlecht, weil beispielsweise ihre Laufzeit sehr groß sein kann. Diese
Diskrepanz liegt darin begründet, dass die klassische Theorie einen
Algorithmus nur dann als gut betrachtet, wenn er im Worst Case, d.h. auf
allen möglichen Eingaben, gute Ergebnisse erzielt. Dass schlechte
Eingaben oft sehr künstliche Eigenschaften aufweisen, die in praktischen
Anwendungen gar nicht auftreten, wird dabei nicht berücksichtigt.

In dem Projekt von Professor Röglin sollen neue Analysemethoden für
Algorithmen entwickelt werden, die nicht mehr nur auf dem Worst Case
beruhen, sondern mit denen man das Verhalten von Algorithmen auf
realistischen Eingaben theoretisch analysieren kann. Dadurch sollen neue
Erkenntnisse über Algorithmen und Optimierungsprobleme gewonnen werden,
die mit klassischen Methoden nicht zu erreichen sind.