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

点击翻译按钮获取中文摘要

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.