Günter Rote - Arbeiten über Optimierungsprobleme

Die Arbeiten Minimizing the density of terminal assignments in layout design und A heuristic for decomposing traffic matrices in TDMA satellite communication behandeln Optimierungsprobleme aus dem industriellen Bereich, bei denen kombinatorische Methoden zum Einsatz kommen. Im ersten Fall handelt es sich um ein Problem aus dem Entwurf höchstintegrierter Schaltkreise (VLSI), im zweiten Fall aus der Satellitenkommunikation.

Die Arbeit Time complexity and linear-time approximation of the ancient two machine flow shop behandelt ein klassisches Problem aus der Zeitplanung (scheduling), für das ein Approximationsschema angegeben wird. Auch die Arbeit Minimizing the number of tardy jobs on a single machine with batch setup times befasst sich mit einem Zeitplanungsproblem, bei dem Aufgaben zweckmäßig in Gruppen zusammengefasst werden sollen, damit die Umrüstzeiten nicht überhandnehmen. Die Arbeit The obnoxious center problem on a tree behandelt ein Standortproblem in einem Baum.

In der Arbeit Optimal logistics for expeditions - the jeep problem with complete refilling wird eine spezielle Variante des sogenannten Jeep-Problems optimal gelöst. Bei diesem Problem soll man mit einem Jeep (oder einer Weltraumexpedition) mit beschränkter Ladekapazität und einer vorgegebenen Treibstoffmenge, die nur am Ausgangspunkt vorhanden ist, möglichst weit kommen, indem man unterwegs Treibstoffdepots anlegt. Die Ursprünge des Jeep-Problems lassen sich im Kern über mehr als 1000 Jahre zurückverfolgen. Die Hauptarbeit bei unserer Lösung ist die Modellierung des Problems als lineares Programm.

Die Arbeit Vehicle routing in an automated warehouse: analysis and optimization beschreibt das Ergebnis einer Zusammenarbeit unseres Instituts mit einem Software-Firma, bei der wir die Optimierungsalgorithmen für die Steuerung eines automatischen Hochregallagersystems mit mehreren Fahrzeugen entwickelt haben.

Die Arbeit A new metric between polygons, and how to compute it behandelt die sogenannte beschränkte Lipschitz-Norm. Diese Norm liefert ein Abstandsmaß zwischen Funktionen oder zwischen konvexen Bereichen der Ebene, das verschiedene wünschenswerte Eigenschaften hat. Die beschränkte Lipschitz-Norm ist ein Spezialfall der Kantorowitsch-Rubinstein-Norm, die in der Wahrscheinlichkeitstheorie und in der Funktionentheorie auftritt. Die Kantorowitsch-Rubinstein-Norm wiederum geht auf Arbeiten von Kantorowitsch aus den 40er-Jahren und von Gaspard Monge aus dem 18. Jahrhundert über das Transportproblem zurück. In der Arbeit stelle ich verschiedene Formulierungen für die beschränkte Lipschitz-Norm dar, die zum Teil unabhängige Anwendungen haben, und ich gebe Algorithmen zur Berechnung der beschränkten Lipschitz-Norm an.

Die Arbeit Flattening a rooted tree löst ein graphentheoretisches Problem, das beim Übersetzen von blockstrukturierten Programmiersprachen (Compilerbau) auftritt. Es handelt sich um die automatische Umstrukturierung von Bäumen, die die Schachtelungsstruktur von Prozeduren darstellen.

Der klassische Huffman-Algorithmus bestimmt den optimale Code zur Übertragung von Informationen mit einem vorgegebenen Alphabet, wenn die Wahrscheinlichkeiten für das Auftreten der einzelnen Informationen bekannt sind. Die Arbeit A dynamic programming algorithm for constructing optimal prefix-free codes for unequal letter costs gibt einen polynomiellen Algorithmus für die Verallgemeinerung dieses Problems an, wo die Buchstaben des Kodierungsalphabetes verschieden lang sein können, wie etwa beim Morse-Alphabet.

In den Bereich der Optimierungsprobleme fallen auch meine Arbeiten zu geometrischen Optimierungsproblemen, insbesondere die Arbeiten zum Rundreiseproblem.

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