Grenzen von Algorithmenparadigmen

点击翻译按钮获取中文摘要

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.