Forschungsprojekt für Algorithmen für schwere Probleme

Exponentialzeitalgorithmen verkörpern geradezu den Bereich praktisch nicht anwendbarer algorithmischer Verfahren. Daher werden für derartige Probleme gerne Heuristiken eingesetzt, die meist keine mathematisch fundierten Leistungsgarantien bieten. Alternativen bieten „parameterisierte Algorithmen“.

Beispiel Speicherchipherstellung: Dort werden oft Rekonfigurationstechniken angewendet, um die Ausbeute bei der Fertigung zu erhöhen. Die zugehörigen Problemstellungen sind nachweislich algorithmisch schwierig. Wir konnten zeigen, dass ein parameteriserter Ansatz unter realistischen Annahmen mit guten Laufzeiten fast immer zu bestmöglichen Lösungen führt. (vgl. G. Bai, H. Fernau. Constraint bipartite vertex cover: Simpler exact algorithms and implementations. Journal of Combinatorial Optimization, 23:331–355, 2012. Die Arbeit fußt auf einer Diplomarbeit an unserem Lehrstuhl.)

Subexponentialzeitalgorithmen: Manche schwere Probleme gestatten zumindest Laufzeitverbesserungen im Exponenten (vgl. J. Alber, H.L. Bodlaender, H. Fernau, T. Kloks, R. Niedermeier. Fixed parameter algorithms for dominating set and related problems on planar graphs. Algorithmica, 33: 461–493, 2002. und J. Alber, H. Fernau, R. Niedermeier. Parameterized complexity: exponential speedup for planar graph problems. Journal of Algorithms, 52:26–56, 2004.)

Problemkerne: Dieser Ansatz gestattet die mathematische Analyse von Datenreduktions-Verfahren, ein recht beliebter heuristischer Ansatz. Möglichkeiten und Grenzen dieser Vorgehensweise beschreibt D. Binkele-Raible, H. Fernau, F.V. Fomin, D. Lokshtanov, S. Saurabh. Kernel(s) for problems with no kernel: on out-trees with many leaves. ACM Transactions on Algorithms, 8 (2012), No. 38.

Beteiligte(r) Wissenschaftler:Prof. Dr. Henning Fernau