Algorithmen mit verfeinerter Worst-Case-Analyse auf der Basis geeigneter Schwierigkeitsbegriffe

• Applicant: Professor Dr. Peter Rossmanith
• Subject Area: Theoretical Computer Science
• Term: from 2004 to 2010
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 5433832

Bei der klassischen Worst-Case-Analyse werden Laufzeiten von Algorithmen relativ zur Eingabelänge gemessen. Diese Vorgehensweise ist für die Klassifikation der jeweiligen Komplexitäten bewährt und zunächst auch ausreichend, liefert aber naturgemäß eine sehr pessimistische Einschätzung. Ein zumindest grundsätzlich erprobter Ansatz zur Handhabung der oftmals großen Diskrepanz zwischen Worst-Case- und tatsächlicher Laufzeit ist die Parametrisierte Komplexitätstheorie. Hier wird die Laufzeit relativ zur Eingabelänge und einem geeigneten Parameter gemessen, wobei dieser Parameter durchaus eine Eigenschaft der Eingabe sein darf, deren Messung selbst ein schwieriges Problem darstellt. Das Anliegen unseres Projektes ist nun die Entwicklung von Algorithmen mit einer noch präziseren Worst-Case-Analyse, bei der Laufzeiten nicht mehr bezüglich der Eingabelänge oder bestimmter Parameter, sondern vielmehr bezüglich der "relativen Schwierigkeit" von Instanzen gemessen werden. Hierzu sollen Schwierigkeitsbegriffe entwickelt werden, die eine stärkere Annäherung der ermittelten Worst-Case- an die tatsächlichen Laufzeiten erlauben.

• DFG Programme: Research Grants