Der bekannteste Optimierungsalgorithmus für das bekannteste Optimierungsproblem ist der Simplex-Algorithmus für Lineares Programmieren.

(LP) maximiere eine lineare Funktion in d Variablen, wobei die Variablen n lineare Ungleichungen erfüllen müssen.

Für die algorithmische Geometrie sind besonders Probleme in kleinen oder sogar konstanten Dimensionen (d = 2,3) interessant, und man interessiert sich deshalb vornehmlich für die Laufzeit von Verfahren als Funktion von n. Für den simplex-Algorithmus (in einer speziellen Variante) gab es dabei seit 1992 sehr interessante Entwicklungen. Es konnte gezeigt werden, daß er optimale Laufzeit O(n) hat (allerdings mit exponentieller Abhängigkeit von d). Wichtiger noch, es stellte sich heraus, daß mit einem einheitlichen, simplex-artigen Algorithmus und gleichen

Zeitschranken auch viele andere Probleme gelöst werden können, für die Linearzeit-Lösungen teilweise nicht bekannt oder nur kompliziert realisierbar waren. Zwei Beispiele sind

(MINIBALL): Finde die kleinste Kugel, die n gegebene Punkte im d-dimensionalen Raum enthält.

(POLYDIST): Gegeben zwei Polytope mit zusammen n Ecken im d-dimensionalen Raum, finde den kürzesten Abstand zwischen den Polytopen.

Zusätzlich konnte das Verhalten in d verbessert werden - es ist `nur' noch exponentiell in sqrt(d).

Die Dissertation beschäftigt sich mit mehreren Aspekten dieser Entwicklung.

1. Welche abstrakten Klassen von Problemen lassen sich simplex-artig lösen? Es zeigt sich, daß man erstaunlich wenig Eigenschaften benötigt, um effiziente Verfahren zu erhalten.
2. Welche Rolle spielt Randomisierung? Das oben erwähnte O(n) Verfahren verwendet Münzwürfe. Das hat den Effekt, daß man es nicht `hereinlegen' und zu sehr schlechter, exponentieller, Laufzeit in d verführen kann, wie das für viele deterministische Verfahren geht.
3. Kann man randomisierte Verfahren im schwächeren Sinne vielleicht doch hereinlegen? Mit anderen Worten, gibt es Eingaben, so daß die Algorithmen nicht polynomiell in n und d sind? Das ist nicht bekannt, und die Analyse ist wesentlich schwieriger als im deterministischen Fall. Die Frage ist eine der heißen offenen Probleme auf diesem Forschungsgebiet.