Entwicklung einer Theorie der "Smoothes Analysis" für diskrete Probleme sowie die Anwendung von "Smoothed Analysis" auf andere Konzepte wie z.B. Approximierbarkeit

• Applicant: Professor Dr. Markus Bläser
• Subject Area: Theoretical Computer Science
• Term: from 2008 to 2014
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 59655297

Smoothed Analysis ist eine neue Analysemethode für die Laufzeit von Algorithmen, die von Spielman und Teng eingeführt wurde, um die gute Performance des Simplex- Algorithmus zu erklären. In einem gewissen Sinne interpoliert die Smoothed Analysis zwischen Worst-Case- und Average-Case-Analyse: Eine Eingabe x wird gestört und es wird untersucht, wie sich die Laufzeit des Algorithmus verhält in Abhängigkeit von der Störung. Wenn das Problem kontinuierlich ist, so scheinen z. B. normalverteilte Störungen natürlich. Bei diskreten Problemen hingegen bietet sich kein natürliches Modell an. Ein Ziel dieses Projekt ist es, geeignete Störmodelle für diskrete Probleme zu finden. Das zweite Ziel ist es, Smoothed Analysis nicht nur auf die Laufzeit anzuwenden, sondern auf andere Maße, z. B. Approximierbarkeit. Schließlich möchten wir eine allgemeine Theorie der Smoothed Analysis für diskrete Probleme entwickeln.

• DFG Programme: Research Grants
• Participating Person: Dr. Bodo Manthey