Aktionsplan-Informatik: Kleine Parameter in schwierigen Problemen: Entwurf, Analyse, Implementierung und Anwendung von Festparameteralgorithmen

• Antragsteller: Professor Dr. Rolf Niedermeier (†)
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2003 bis 2010
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 5401637

Festparameteralgorithmen entwickelten sich im Laufe der letzten Jahre zu einer sinnvollen, ernstzunehmenden Alternative zu Heuristiken und Approximationsalgorithmen bei der Lösung kombinatorisch schwieriger, im allgemeinen viel Rechenzeit erfordernder Probleme. Kernidee bei der Lösung derartiger Probleme mithilfe von Festparameteralgorithmen ist die Beschränkung der offenbar unumgänglichen "kombinatorischen Explosion" auf problemspezifische Parameter. Damit lassen sich optimale Lösungen harter Probleme in oftmals praktisch erträglichen Laufzeiten berechnen. Das Projekt PIAF strebt eine praxisbezogene Untersuchung des in der Forschungslandschaft zunehmend Umfang gewinnenden Gebiets der Festparameteralgorithmen an, wobei Implementierungen und experimentelle Untersuchungen mit Praxisdaten gleichermaßen miteinfließen sollen. Thematisch wird eine anwendungsorientierte Konzentration auf Kerntechniken wie z.B. Datenreduktion durch effiziente Vorverarbeitung der Eingabe und die praxisnahe Untersuchung von Fundamentalproblemen der kombinatorischen Optimierung wie VERTEX COVER oder DOMINATING SET (besonders mit ihren in der Praxis auftretenden Abwandlungen) angestrebt. Der Verfolgung von Bezügen zu angrenzenden Gebieten wie Approximation und Heuristik wird großes Gewicht beigemessen.

• DFG-Verfahren: Emmy Noether-Nachwuchsgruppen (Aktionsplan Informatik)