MENÜ
Lineare Optimierung mit dem Schatteneckenalgorithmus im Kontext probabilistischer Analysen
Augsburger Schriften zur Mathematik, Physik und Informatik , Bd. 26
Emanuel Schnalzger
ISBN 978-3-8325-3788-3
225 pages, year of publication: 2014
price: 42.00 €
Lineare Optimierung mit dem Schatteneckenalgorithmus im Kontext probabilistischer Analysen
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.
