Grenzen von Algorithmenparadigmen

• Antragsteller: Professor Dr. Georg Schnitger
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2010 bis 2014
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 170530402

Fundamentale Algorithmenparadigmen - wie Greedy Algorithmen, Backtracking Algorithmen, Branch-and-Bound bzw. Branch-and-Cut Algorithmen oder lokale Suche - sollen untersucht werden.Das Ziel ist eine systematische Untersuchung von Nachweismethoden absoluter unterer Schranken für Entscheidungs- und Optimierungsprobleme. Insbesondere soll die Anwendbarkeit mächtiger Methoden der Schaltkreiskomplexität, der Kommunikationskomplexität und der Beweiskomplexität für die Analyse dieser Algorithmenmodelle untersucht werden.

• DFG-Verfahren: Sachbeihilfen