Parameterisierte Komplexität geometrischer Probleme

• Antragsteller: Professor Dr. Christian Knauer
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2008 bis 2021
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 75015394

Die algorithmische Geometrie ist ein etabliertes Teilgebiet der Algorithmenforschung. Sie beschäftigt sich mit Problemen für geometrische Objekte, wie z.B. Problemen auf geometrischen Graphen, geometrischen Packungs- und Überdeckungsproblemen, Bewegungsplanungsproblemen oder geometrischen Mustererkennungsproblemen. Das Spektrum potentieller Anwendungen ist sehr breit und umfasst graphische Datenverarbeitung, Computersehen, Bildverarbeitung, geografische Informationssysteme und Robotik. In der Regel untersucht die algorithmische Geometrie die Komplexität der betrachteten (Optimierungs-)Probleme im Rahmen der klassischen Komplexitätstheorie. Während dabei für viele grundlegende Probleme gezeigt werden konnte, dass sie effiziente (polynomielle) Lösungen erlauben, wurden viele andere als NP-schwer eingestuft. In den letzten Jahren wuchs das Interesse an einer Theorie zur systematischen Untersuchung von Algorithmen für NP-schwere kombinatorische Probleme. Zu diesem Zweck wurde die Theorie der parametrisierten Komplexität entwickelt. Basierend auf der Beobachtung, dass "reale" Probleme häufig (implizit oder explizit) mit einem oder mehreren Parametern assoziiert sind, misst diese Theorie die Komplexität solcher Probleme nicht nur relativ zur Eingabegröße, sondern zusätzlich in Abhänigigkeit von den relevanten Parametern. Das klassische Modell für effizient lösbare Probleme wird in der parametrisierten Komplexitätstheorie dahingehend erweitert, dass auch ein superpolynomieller Algorithmus als effiziente Lösung eines NP-schweren Problems betrachtet wird, solange diese "Superpolynomialität" nur von den relevanten Parametern bestimmt wird. Die Motivation dahinter ist, dass man hofft, in konkreten Anwendungen typischerweise nur mit "kleinen" Parametern konfrontiert zu werden, so dass die parametrisierten Algorithmen für diese Anwendungen tatsächlich praktikabel und schnell sind. Die parametrisierte Komplexitätstheorie ist für kombinatorische (ibs. graphentheoretische) Probleme wesentlich weiter entwickelt als für geometrische Szenarien. Es gibt eine Vielzahl von geometrischen Problemen deren parametrisierte Komplexität derzeit völlig unbekannt ist. Ziel des Projektes ist eine systematische Untersuchung der parametrisierten Komplexität geometrischer Probleme.

• DFG-Verfahren: Sachbeihilfen