Small parameters in hard problems: Design, analysis, implementation and application of fixed-parameter algorithms

• Applicant: Professor Dr. Rolf Niedermeier (†)
• Subject Area: Theoretical Computer Science
• Term: from 2003 to 2010
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 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 Programme: Independent Junior Research Groups