Kurzfassung

---

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...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 approximativ) 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 Marcator-Fellow unterstützt werden.
» weiterlesen» einklappen

---

---

---

---

---

---

---

---

---

---