Parameterisierte Approximation - neue Konzepte und neue Anwendungen

• Antragsteller: Professor Dr. Henning Fernau
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2014 bis 2018
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 259237183

Vor 40 Jahren wurde im Rahmen der Entwicklung der Theorie der NP-Vollständigkeit für zahlreiche (kombinatorische) Probleme gezeigt, dass diese wohl keine effizienten Lösungsverfahren besitzen können. Allgemein wird davon ausgegangen, dass die Klasse P der von deterministischen Algorithmen in Polynomzeit entscheidbaren Problemen von NP verschieden ist.Diese Frage gilt jedoch als eine der wichtigsten ungelösten mathematischen Fragen überhaupt.Da diese Probleme oft praktisch relevante Fragen modellieren, wurde nach Auswegen gesucht, um dennoch anwendbare Lösungen mit mathematisch befriedigenden Garantien zu erhalten. Dies führte einerseits (seit etwa 50 Jahren) zur Entwicklung von Polynomzeitalgorithmen, die nicht mehr exakte, sondern nur noch angenäherte Lösungen bestimmen, für die man aber dennoch Gütegarantien beweisen kann, und andererseits (in den letzten knapp 20 Jahren) zur Entwicklung von parameterisierten exakten Algorithmen, bei denen die anscheinend unabwendbare kombinatorische Explosion auf einen wohlbestimmten Teil der Eingabe, den sogenannten Parameter, beschränkt bleibt. Angesichts der komplexitätstheoretisch beweisbaren Grenzen dieser beiden Ansätze erscheint es naheliegend, diese zu kombinieren.Dies führte in den letzten Jahren zur Betrachtung von parameterisierten Approximationsverfahren.Jene stecken noch in ihren Anfängen. Wir wollen in diesem Projekt neue Ansätze für derlei Algorithmen suchen. Beispielsweise fußen Polynomzeitapproximationen häufig auf Methoden der Mathematischen Optimierung (z.B.: ganzzahlige Lineare Programme (ILP)), während parameterisierte Algorithmen (seien sie exakt oder auch approximati) auf anderen Prinzipien beruhen. Eine naheliegende Forschungsfrage ist daher, ob und auch wie sich z.B. ILP-Methoden für die parameterisierte Approximation einsetzen lassen.Andererseits gibt es algorithmische Ideen wie die iterative Kompression, die für exakte parameterisierte Algorithmen sehr wichtig sind, bislang aber keinen konkreten Einsatz für die parameteresierte Approximation gefunden haben. Ob oder inwiefern dies geht, wäre eine weitere methodologische Forschungsfrage.Um diese methodologischen Ziele zu erreichen, werden wir uns um konkrete kombinatorische Probleme kümmern. Diese möchten wir in erster Linie aus dem Bereich der Datensicherheit gewinnen.Dies liegt einerseits darin begründet, dass dieser Bereich unlängst eine deutlich vermehrte öffentliche Aufmerksamkeit erlangt hat, andererseits es bislang aber keine systematische Untersuchung der innewohnenden kombinatorischen Probleme gibt.Wir beantragen im Wesentlichen eine Stelle für eine Doktorandin, die sich durch ihr Doppelstudium der Informatik und Mathematik besonders für die anstehenden Aufgaben qualifiziert hat.Sowohl die Modellbildung als auch die Problemlösung im Sinne exakter und approximativer Verfahren soll von einem in diesen Bereichen ausgewiesenen Mercator-Fellow unterstützt werden.

• DFG-Verfahren: Sachbeihilfen