Günter Rote - Arbeiten über konvexe Approximation

In einigen Arbeiten habe ich mich mit der Approximation konvexer Mengen und konvexer Funktionen beschäftigt, insbesondere mit dem Sandwich-Algorithmus. Der Sandwich-Algorithmus ist ein einfacher adaptiver Algorithmus, der eine stückweise lineare Approximation schrittweise durch Hinzunahme neuer Stützstellen verbessert. Die Anregung zu diesen Fragen kam zum Teil aus Optimierungsproblemen, während die Approximationsprobleme selbst durchaus geometrischen Charakter haben.

Die beiden Hauptarbeiten zum Sandwich-Algorithmus, The convergence rate of the Sandwich algorithm for approximating convex functions und Sandwich approximation of univariate convex functions with an application to separable convex programming, untersuchen die Konvergenzgeschwindigkeit des Sandwich-Algorithmus. Der Sandwich-Algorithmus kann auf Funktionen mehrerer Variablen verallgemeinert werden. Eine Analyse scheint jedoch in höheren Dimensionen schwierig zu sein.

Die beiden kleineren Arbeiten Approximation of convex curves with application to the bicriterial minimum cost flow problem und Algorithmische Untersuchungen zu bikriteriellen kostenminimalen Flüssen in Netzwerken sind vorwiegend numerischen Untersuchungen zu diesem Thema gewidmet.

In der Arbeit Simultaneous inner and outer approximation of shapes wird das Problem behandelt, für einen Eibereich ein eingeschriebenes Dreieck und ein dazu homothetisches (ähnliches und gleichgerichtetes) umgeschriebenes Dreieck zu finden, sodass der Vergrößerungsfaktor zwischen den beiden Dreiecken möglichst klein ist. Die Motivation für dieses Problem kommt von dem Wunsch nach adaptiven Algorithmen, deren Laufzeit nicht bloß von der Größe der Eingabe abhängt, sondern die auch auf die "Schwierigkeit" oder "Leichtigkeit" der Eingabe entsprechend reagieren. Der Zusammenhang zum Approximationsproblem ist in der Arbeit erklärt. Neben einem Algorithmus zur Berechnung des optimalen Dreiecks enthält die Arbeit als interessantes mathematisches Nebenergebnis die Bestimmung des schlechtesten möglichen Vergrößerungsfaktors, den man erhalten kann, wenn man als inneres Dreieck das flächengrößte eingeschriebene Dreieck nimmt.

Die Arbeit Approximation of convex figures by pairs of rectangles behandelt das analoge Problem für die Approximation durch Rechtecke.

zum Überblick
Zuletzt geändert am 5. April 2002.