Probabilistische Analyse von Optimierungsalgorithmen

Optimierungsalgorithmen errechnen aus Angaben zu Entscheidungsmöglichkeiten Entscheidungsvorschläge. Qualitätskriterien sind dabei Genauigkeit, Rechenzeit und Speicherplatzbedarf. Die klassische Mathematik beurteilte Algorithmen nach ihrem Verhalten im schlechtestmöglichen Fall. In diesem Forschungsgebiet wird versucht, das Verhalten im Normalfall oder das durchschnittliche Verhalten zur Beurteilung der Algorithmen heranzuziehen. Dazu geht man von einer zufällligen Verteilung der Problemdaten aus und leitet daraus Mittel- und Durchschnittswerte für die Qualität des Verhaltens ab. Für die probabilistische Analyse des Simplexverfahrens zur Lösung linearer Optimierungsprobleme wurde 1982 der Lanchester-Preis für die beste Veröffentlichung in Operations Research verliehen.