Lineare Optimierung Mit Dem Schatteneckenalgorithmus Im Kontext Probabilistischer Analysen

Das Simplexverfahren, welches 1951 von George Dantzig veroffentlicht wurde, hat sich aufgrund seiner niedrigen Laufzeit im praktischen Einsatz zu einem etablierten Losungsverfahren fur lineare Optimierungsprobleme entwickelt. Es konnte jedoch auch gezeigt werden, dass unter sehr ungunstigen Umstanden der Algorithmus extrem viel Zeit bis zur Losungsfindung benotigt. Diese Diskrepanz motiviert die Durchfuhrung sogenannter probabilistischer Laufzeituntersuchungen. Hierbei sind im Wesentlichen die Average-Case-Analyse und die sogenannte Glattungsanalyse zu nennen. Bei der Glattungsanalyse wird untersucht, wie sich die mittlere Laufzeit des Algorithmus in einer gewissen Umgebung um eine beliebige Eingabe verhalt. Motiviert durch die bisher durchgefuhrten Glattungsanalysen des Simplexverfahrens von Spielman und Teng sowie Vershynin, in die randomisierte Vorgehensweisen einfliessen, wird ein deterministisches Gesamtverfahren auf Basis des Schatteneckenalgorithmus vorgestellt und auf seine geglattete Laufzeit hin untersucht. Daruber 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 niederschlagt.