Kombinatorische Approximations Algorithmen

Im Prinzip können Computer Programme *alle* algorithmischen Probleme und *alle* Optimierungsprobleme der "wirklichen" Welt lösen, soferne sie (a) ausreichende Rechenzeit und Speicherkapazität, und (b) vollständige Information über die Problemdaten zur Verfügung haben. In der Praxis sind diese Bedingungen aber oft nicht erfüllt, da man im allgemeinen weder 200 Jahre auf ein Rechenergebnis warten will, noch Informationen über den morgigen Systemzustand zur Verfügung hat. In diesen Fällen gibt man sich dann mit sogenannten Approximationslösungen zufrieden, d.h. mit Lösungen, die "vernünftig nahe" bei der optimalen Lösung liegen, und die einfach zu finden sind. Im Rahmen des Projekts wird nun untersucht, wie nahe man mit wenig Zeit und mit unvollständiger Information ans Optimum herankommen kann. Rechenzeit und Qualität einer Lösungsprozedur werden in der Begriffswelt der Theoretischen Informatik ausgedrückt und bewertet.

In diesem Projekt haben wir die Approximierbarkeit einer großen Anzahl von kombinatorischen Optimierungsproblemen analysiert. Die meisten dieser Optimierungsprobleme stammen aus dem Gebiet der Reihefolgeplanung von Prozessen, aus dem Gebiet der Graphen und Netzwerke, und aus dem Gebiet der Standort Planung. Wir haben positive und negative Resultate erzielt: Die positiven Resultate sind Approximations\-algorithmen und Approximations\-schemata, die innerhalb vernünftiger Laufzeit eine Lösung finden, die vernünftig nahe bei der Optimallösung liegt. Die negativen Resultate betreffen die Nicht-Existenz von schnellen Approximations\-algorithmen für gewisse Optimierungsprobleme unter gewissen Annahmen aus der Komplexitätstheorie. Alle unsere Resultate sind theoretischer Natur und betreffen die Grundlagen der Berechenbarkeits\-theorie. Daher haben sie keine direkten Anwendungen in Wirtschaft, Gesellschaft, und Kultur. In den meisten unserer Resultate untersuchen wir isolierte Probleme, und leiten spezialisierte Ergebnisse her, die auf den spezifischen Eigenschaften dieser Probleme aufbauen. In einem unserer allgemeineren Hauptresultate karakterisieren wir die Situationen, in denen eine gewisse Daten-Rundungs-Methode zu Approximations\- algorithmen mit beliebig guter Qualität führt (ein sogenanntes FPTAS). Dies ergibt dann eine einheitliche Theorie von Dynamischen Programmen, die in ein FPTAS transformiert werden können. Außerdem haben wir eine strukturelle Analyse der Approximations\-schemata in der Literatur durchgeführt und sie in drei Grundtechniken eingeteilt: Runden der Input-Daten, Strukturierung des Output- Raumes, und Vereinfachung der Daten, die während der Ausführung eines exakten Algorithmus gespeichert werden.