Lineare Optimierung mit dem Schatteneckenalgorithmus im Kontext probabilistischer Analysen
Emanuel Schnalzger
Das Simplexverfahren, welches 1951 von George Dantzig veröffentlicht wurde, hat sich aufgrund seiner niedrigen Laufzeit im praktischen Einsatz zu einem etablierten Lösungsverfahren für lineare Optimierungsprobleme entwickelt. Es konnte jedoch auch gezeigt werden, dass unter sehr ungünstigen Umständen der Algorithmus extrem viel Zeit bis zur Lösungsfindung benötigt. Diese Diskrepanz motiviert die Durchführung sogenannter probabilistischer Laufzeituntersuchungen. Hierbei sind im Wesentlichen die Average-Case-Analyse und die sogenannte Glättungsanalyse zu nennen.
Bei der Glättungsanalyse wird untersucht, wie sich die mittlere Laufzeit des Algorithmus in einer gewissen Umgebung um eine beliebige Eingabe verhält. Motiviert durch die bisher durchgeführten Glättungsanalysen des Simplexverfahrens von Spielman und Teng sowie Vershynin, in die randomisierte Vorgehensweisen einfließen, wird ein deterministisches Gesamtverfahren auf Basis des Schatteneckenalgorithmus vorgestellt und auf seine geglättete Laufzeit hin untersucht.
Darüber hinaus wird das Average-Case-Prinzip in Verbindung mit dem Rotationssymmetriemodell, welches in dieser Kombination bereits in den Untersuchungen von Borgwardt Verwendung fand, aufgegriffen und in diesem Zusammenhang der Frage nachgegangen, wie sich der klassische Zwei-Phasen-Ansatz des Simplexverfahrens auf die durchschnittliche Laufzeit niederschlägt.
