Parametrisierte Algorithmik

• Applicant: Professor Dr. Rolf Niedermeier (†)
• Subject Area: Theoretical Computer Science
• Term: from 2007 to 2011
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 65062910

Das Hauptforschungsgebiet des Antragstellers ist die parametrisierte Algorithmik NPschwererProbleme. Aus seiner vielfach in der Literatur zitierten Habilitationsschrift [28]entwickelte sich durch eine deutliche Verbreiterung des Themenspektrums die Lehr- undForschungsmonographie „Invitation to Fixed-Parameter Algorithms“, die im Februar 2006bei Oxford University Press erschien [29]. Sie ergänzt sich mit der stärker komplexitätstheoretischorientieren Monographie „Parameterized Complexity Theory“ von Flum undGrohe [14] zu der grundlegenden Basis des recht neuen, dynamisch sich weiterentwickelndenForschungsgebiets der parametrisierten Algorithmik. Beide lösen damit quasidas in mancher Hinsicht etwas überaltete, relativ schwer lesbare Werk von Downey undFellows [9] ab.Im Oktober 2004 folgte der Antragsteller einem Ruf von der Stelle eines Emmy-Noether-Nachwuchsgruppenleiters in Tübingen (Aktionsplan Informatik der DFG, seit2002) auf die C4-Professur Theoretische Informatik I (Nachfolge Prof. Gerd Wechsung)an die Universität Jena. Seither wurde in Jena ein grundlegender Neuaufbau der TheoretischenInformatik betrieben, der die Forschungszeit unter wünschenswertesMaß zusammenschmelzenließ. Dennoch konnte die Arbeitsgruppe in Sachen Forschung internationalesNiveau halten. Vermöge eines Forschungssemesters mit gleichzeitiger Zusammenarbeitmit Prof. Michael R. Fellows vor Ort soll nun der Sprung auf eine internationalherausragende Postition mit einhergehender thematischer Innovation (wie Erschließungneuer Themenfelder und Techniken) im besagten Forschungsgebiet betrieben werden.Besonderes Augenmerk für die konkrete Forschung mit Fellows wird algorithmischenTechniken wie Datenreduktion und Iterativer Kompression und Anwendungsgebieten wieBioinformatik oder „Computational Social Choice“ gelten.Darüberhinaus soll versucht werden, die bislang vielfach vereinzelt wirkenden JenaerForschungskräfte im weiten Feld der angewandten Algorithmik zu einem gemeinsamenVerbundprojekt zusammenzuführen. Dies wird auch stark von der Universitätsleitung gefordert,da es in der Jenaer Informatik seit ihrer Gründung Anfang der Neunziger Jahredes letzten Jahrhunderts bisher noch kein gemeinsames, größeres Verbundforschungsprojekt(wie z.B. Forschergruppe oder Graduiertenkolleg) gab. Mit einer Reihe vorwiegendneuberufener Kollegen schiene ein solcher Qualitätssprung nach vorne auch möglich.

• DFG Programme: Research Grants