Neue Herausforderungen in der parametrisierten Komplexität

Das Design von effizienten Algorithmen für verschiedene Berechnungsprobleme ist ein fundamentaler Bestandteil der Informatik. Während viele wichtige Probleme im Allgemeinen keine effizienten Algorithmen erlauben, enthalten praktische Instanzen oft eine versteckte Struktur die es erlaubt diese Probleme in der Praxis dennoch effizient zu lösen. Die Konzepte der parametrisierten Komplexität stellen die perfekten Werkzeuge und Techniken bereit um solche versteckten Strukturen zu formalisieren, quantifizieren und für die effiziente Lösung von Problemen mit rigorosen Laufzeitgarantien einzusetzen. Parametrisierte Komplexität wurde bereits in vielen Bereichen der Informatik mit grossem Erfolg angewendet. Allerdings gibt es immer noch einige prominente Bereiche der Informatik in denen wir ein genaues Verständnis der Anwendbarkeit der parametrisierten Komplexität vermissen. Wir schlagen deshalb eine gründliche Untersuchung zweier solcher "high-impact" Bereiche mittels der parametrisierten Komplexität vor: Ganzahlige Lineare Optimierung und Maschinelles Lernen. Als Resultate erwarten wir effiziente Algorithmen die in der Lage sind natürliche Strukturen zu nutzen um exakte Lösungen für schwierige Probleme in diesen wichtigen Bereichen der Informatik zu finden.

Das Entwickeln effizienter Algorithmen für unterschiedliche Berechnungsprobleme ist einer der fundamentalen Bereiche der Informatik. Obwohl für viele wichtige Berechnungsprobleme keine effizienten Algorithmen möglich sind, sofern wir allgemeine Eingaben betrachten, enthalten in der Praxis auftretende Instanzen oft eine verborgene Struktur, die für die effiziente Lösung solcher Berechnungsprobleme ausgenutzt werden kann. Das Paradigma der Parametrisierten Komplexität bietet die perfekten Werkzeuge und Techniken, um verschiedenste Formen von Struktur zu formalisieren, quantifizieren und zu benutzen. Das erlaubt das effiziente Lösen underschiedlicher allgemein schwieriger Probleme innerhalb von Laufzeitgarantien. Wir haben eine rigorose Untersuchung fundamentaler Probleme in einer Vielzahl von entwicklungsstarken Bereichen der Informatik durchgeführt, insbesondere in Ganzzahliger Linearer Optimierung, Künstlicher Intelligenz und Maschinellem Lernen. Die erzielten Ergebnisse umfassen nicht nur neue Algorithmen mit starken Gütegarantien und ein tiefgehendes Verständnis des komplexitätstheoretischen Verhaltens einer Reihe von Problemen in diesen Bereichen, sondern auch neue, universell andwendbare Techniken und Werkzeuge, die wir darüber hinaus erfolgreich auf Probleme in Bereichen wie Graphzeichnung, Computational Social Choice Theory und Graphentheorie angewandt und so unser Verständnis vertieft von diesen vertieft haben. Insgesamt hat dieses Projekt zu 62 Veröffentlichungen in wissenschaftlichen Journalen und Konferenzbänden beigetragen.