Project Details
Projekt Print View

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

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
 
 

Additional Information

Textvergrößerung und Kontrastanpassung