Pragmatische Parametrisierte Algorithmen

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

Das übergeordnete Ziel dieses Projektes ist es, eine Brücke zwischen den rein theoretischen Algorithmen und den Heuristiken zu schlagen, also zwischen solchen Algorithmen, die zwar optimale Lösungen ausgeben, aber in der Praxis nicht eingesetzt werden können, und jenen Algorithmen, welche in der Praxis zwar auf breiter Front eingesetzt werden, aber oft suboptimale Lösungen ausgeben. Insbesondere möchten wir im Rahmen dieses Projekts effiziente Algorithmen entwickeln, die (1) implementierbar sind und unter realen Bedingungen eingesetzt werden können und (2) dennoch - im Vergleich mit den bekannten asymptotisch schnellsten Algorithmen - wettbewerbsfähig oder sogar schneller sind. Der Forschungsschwerpunkt besteht insbesondere in der Entwicklung neuer Techniken für den Entwurf von Algorithmen und in der Verbesserung bestehender Techniken, so dass existierende Hürden auf dem Weg der praktischen Anwendbarkeit genommen werden können. Die Techniken, die wir entwickeln möchten, mögen ihrerseits recht komplex oder gar von der Art eines Meta-Theorems sein. Wir sind jedoch hauptsächlich an solchen interessiert, die sich prinzipiell unter realen Bedingungen einsetzen lassen - hinsichtlich des Aufwands für die Implementierung, des Speicherverbrauchs sowie der Laufzeit. Indem wir transparente Schranken für die Laufzeit und den verwendeten Speicher angeben, insbesondere mit polynomiellen und konstanten Faktoren innerhalb von vernünftigen Bereichen, möchten wir das bekannte Repertoire von jenen Algorithmen erweitern, die sich dazu eignen, unter praktischen Gesichtspunkten in der Industrie eingesetzt zu werden.

• DFG-Verfahren: Sachbeihilfen