Theoretische Analyse der Robustheit stochastischer Optimierungsprozesse

• Applicant: Professorin Dr. Beate Bollig, since 2/2010
• Subject Area: Theoretical Computer Science
• Term: from 2005 to 2012
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 15253112

Randomisierung hat sich als Schlüsselkonzept in vielen Bereichen der Informatik erwiesen, insbesondere gilt dies für die Bearbeitung von Optimierungsproblemen. Ein randomisierter Algorithmus definiert einen stochastischen Optimierungsprozess, der effizient, aber auch robust sein soll. Folgende Aspekte von Robustheit sollen exemplarisch untersucht werden: Robustheit gegenüber ¿ Erweiterungen der Eingabemenge, modelliert durch semizufällige Eingabeverteilungen, ¿ Fehlern bei der Funktionsauswertung, Änderungen der Problemparameter und Einschränkungen der verwertbaren Information. Darüber hinaus ist es oft schwierig, die Parameter randomisierter Algorithmen geeignet einzustellen. Daher stellt sich die Frage, wie robust der Algorithmus gegenüber Änderungen seiner eigenen Parameter ist und welche Parameter oder Module essenziell für die Bearbeitung des Problems sind. Die verschiedenen Robustheitsaspekte sollen exemplarisch für ausgewählte Probleme untersucht werden, auch um nachzuweisen, dass sie methodisch einheitlich bearbeitet werden können. Dabei werden sowohl problemspezifische Algorithmen als auch allgemeine Suchheuristiken analysiert.

• DFG Programme: Research Grants
• Ehemaliger Antragsteller: Professor Dr. Ingo Wegener, until 2/2010 (†)