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

点击翻译按钮获取中文摘要

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.