Forschungsprojekte
Lösungsqualität und Effizienz in der diskreten Optimierung
Für viele praktisch relevante Optimierungsprobleme ist es im Allgemeinen zu aufwändig, eine optimale Lösung oder auch nur eine Approximation davon zu berechnen, Ein gängiger Ansatz zur Behandlung solcher Probleme ist der Entwurf von Approximationsalgorithmen fur eingeschränkte Klassen von Eingabeinstanzen. Das Konzept der Approximationsstabilität erlaubt es uns zu messen, in welchem Umfang solche Algorithmen auch für erweiterte Klassen von Eingaben brauchbar sind. Wir untersuchen dies Konzept der Stabilität für verschiedene wichtige Optimierungsprobleme, zum Beispiel das Traveling-Salesman-Problem oder Zusammenhangsprobleme in Graphen, in denen eine erweiterte Form der Dreiecksungleichung gilt.
Advice-Komplexität von Online-Algorithmen
In dem Modell der Online-Probleme bekommt ein Algorithmus seine Eingabe stückweise und muss für jeden erhaltenen Teil der Eingabe einen Teil der endgültigen Ausgabe zurückgeben. Das überwiegend genutzte Mass, um die Güte eines solchen Online-Algorithmus zu messen, ist die kompetitive Güte, die die Kosten einer berechneten Lösung mit den Kosten einer optimalen Offline-Lösung vergleicht, also mit einer Lösung, die berechnet wird, nachdem die vollständige Eingabe zur Verfügung steht. In diesem Projekt schlagen wir ein anderes Mass für Algorithmen vor, die während ihrer Berechnung mit partieller Information auskommen müssen. Wir erwarten, dass dieses Mass zu einem besseren Verständnis der Natur der Online-Probleme führt.
Berechnungskomplexität der Reoptimierung
In diesem Projekt betrachten wir das folgende Reoptimierungsszenario: Gegeben ist eine Instanz eines schweren Optimierungsproblems zusammen mit einer optimalen Lösung. Nun wollen wir eine gute Lösung für eine lokal veränderte Eingabeinstanz finden. Dies führt auf natürliche Weise zu der Frage, ob die Kenntnis der optimalen Lösung für die ursprüngliche Instanz helfen kann, die modifizierte Instanz zu lösen. Wir betrachten verschiedene wichtige Optimierungsprobleme in diesem Rahmen, zum Beispiel das Steinerbaum-Problem oder das Problem des kürzesten Superstrings.
Computation Power of Randomization and Nondeterminism
The fundamental questions of computation theory are related to the relative power of determinism, nondeterminism, and randomization. Currently, one is not able to solve problems about the relations between deterministic, randomized, and nondeterministic polynomial-time classes, and our methods are not powerful enough to give us a realistic chance to attack these problems seriously. Instead, we are trying to estimate the relations between determinism, nondeterminism, and different modes of randomization in distinct restricted frameworks within this project, in order to gain experience with different computation modes and a deeper understanding of the nature of randomization and nondeterminism.