Optimierung unter explorierbarer Unsicherheit

• Antragstellerin: Professorin Dr. Nicole Megow
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2023
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 517912373

Beim Lösen von Optimierungsproblemen in der Praxis sind typische Hürden die Unsicherheit in den Eingabedaten oder gar das Fehlen von Informationen. Das Gebiet der Optimierung unter explorierbarer Unsicherheit befasst sich mit Problemen, bei denen unsichere Eingabedaten durch Abfrageoperationen (Queries) ermittelt werden können. Solche Queries sind mit Zusatzkosten verbunden und daher soll deren Anzahl minimiert werden. Wichtige Fragen sind: Welche Eingabeelemente sollen abgefragt werden? Welche Informationen sind erforderlich, um eine bestimmte Lösungsqualität für das zugrundeliegende Optimierungsproblem zu erzielen? Ziel dieses Projekts ist es, neue Techniken zur Optimierung unter explorierbarer Unsicherheit zu entwickeln und den Tradeoff zu analysieren zwischen den Kosten für die Exploration und dem Nutzen für die Lösungsqualität. Unser Schwerpunkt liegt auf dem Entwurf von Algorithmen mit mathematischen Garantien an die Lösungsgüte. Wir untersuchen parallele und damit weniger adaptive Query-Strategien sowie neue Modelle jenseits der klassischen Worst-Case-Betrachtungen, wie stochastische Modelle sowie neue lernbasierte Algorithmen.

• DFG-Verfahren: Sachbeihilfen