Intuitive Strategien zur Lösung von Graph- und Erfüllbarkeitsproblemen

• Antragsteller: Professor Dr. Peter Rossmanith
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2005 bis 2011
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 17935491

Unter Verwendung des graphentheoretischen Konzepts der Baumweite ist es uns gelungen, eine neue Methode zu entwickeln, mit der sehr unterschiedliche Probleme auf einheitliche Art vereinfacht werden können. Die Grundidee besteht darin, wiederholt an lokal als günstig erscheinenden Stellen rekursiv zu verzweigen, bis schließlich eine einfache Instanz übrigbleibt. Das besondere an unserer Methode ist, daß wir die Analyse an der Anzahl der Kanten eines entsprechenden Graphen ausrichten. Dieser Ansatz wurde bisher nicht betrachtet und ermöglicht es uns zu beweisen, daß wir bei obigem Verfahren nur selten verzweigen müssen. Die Anwendung dieser neuen Idee führte bereits mit geringem Aufwand zu konkurrenzfähigen Verfahren zur Lösung bestimmter Optimierungsprobleme auf Graphen und logischen Formeln, wobei sich die Anwendbarkeit auf Formeln jeweils dadurch ergibt, daß sie in geeigneter Weise durch Graphen repräsentiert werden können. Wir beabsichtigen, sowohl die Methode als auch ihre Anwendungen weiterzuentwickeln. Nach unserer Einschätzung haben wir gerade erst begonnen, das Potential dieses Konzeptes auszuschöpfen. Die Anwendung dieser Erkenntnisse führt insbesondere zu intuitiven Algorithmen, die effizient und doch sehr einfach sind. Gemeint sind damit vor allem Verfahren, deren Wirksamkeit zwar intuitiv einleuchtend, aber formal nichttrivial zu analysieren ist. Dabei erlaubt unsere Vorgehensweise nun vor allem, für solche simplen Heuristiken beweisbare Laufzeitschranken anzugeben, die jenen deutlich komplizierterer Algorithmen nicht oder kaum nachstehen. Es bietet sich daher an, neue Algorithmen zu entwerfen und zu analysieren und dabei dem klassischen Kriterium der asymptotischen Laufzeit das Entwicklungsziel der Einfachheit beiseite zu stellen.

• DFG-Verfahren: Sachbeihilfen