Die Kunst der Differenzparametrisierung in der multivariaten Algorithmik

• Antragsteller: Dr. André Nichterlein, seit 6/2022
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2021
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 452214352

Wir streben praktisch aussagekräftigere Resultate über die Leistung (Effizienz) von exakten parametrisierten Algorithmen (FPT) für NP-schwere Probleme an. Der Kernzugang soll hierbei über sogenannte "Differenzparametrisierungen" erfolgen, welche auf natürliche Weise das bekannte Konzept des Parametrisierens über einem garantierten Schwellwert verallgemeinern. In dem Zusammenhang wird der Schwerpunkt der Untersuchungen auf Suchbaumalgorithmen und Datenreduktionstechniken als algorithmische Kernwerkzeuge und auf Methoden der parametrisierten Komplexitätsanalyse als theoretische Kernwerkzeuge liegen. Dabei verfolgen wir im wesentlichen folgende Untersuchungslinien:- das Studium von Differenzparametern die sich durch das "Packen kombinatorischer Strukturen" und damit einhergehender unterer Schranken ergeben; - das Studium von Differenzparametern die sich durch Approximationsalgorithmen (einschließlich lineares Programmieren) ergeben; - das Studium von Differenzparametern die sich durch die systematische Durchmusterung von Parameterhierarchien ergeben; und - das Studium von Linearkombinationen von Parametern, welche allgemein das Konzept von Differenzparametern weiter verallgemeinern.Das Projektkernziel ist es somit, die "Kunst der Problemparametrisierung" wesentlich voran zu treiben. Dabei soll zum einen die Leistung insbesondere von Branch&Bound-Algorithmen besser erklärt werden können und zum anderen algorithmische Lösungsansätze unter Ausnutzung verfeinerter Parametrisierungen verbessert werden. Dabei sollen sich unsere Untersuchungen hauptsächlich auf NP-schwere Graphprobleme beziehen.

• DFG-Verfahren: Sachbeihilfen
• Ehemaliger Antragsteller: Professor Dr. Rolf Niedermeier, bis 6/2022 (†)