Prof. Dr. Sebastian Pokutta, Leiter der Arbeitsgruppe „Mathematische Optimierung“ am Institut für Mathematik und Mitglied des Exzellenzclusters MATH+, und seinen Co-Autoren wurde Ende Juni 2023 der renommierte Gödel-Preis verliehen in Anerkennung für ihre einflussreiche Arbeit in der kombinatorischen Optimierung [1].
In ihrer preisgekrönten Arbeit lösen Fiorini, Massar, Pokutta, Tiwary und de Wolf ein 20 Jahre altes Problem und liefern damit einen bahnbrechenden Beitrag für die kombinatorischen Optimierung. Sie bewiesen, dass jedes lineare Programm, das das berüchtigte Travelling Salesman Problem beschreibt, exponentiell groß sein muss. Damit setzte sie eine endgültige Grenze für die Anwendung der linearen Programmierung auf diese Art komplexer Rechenprobleme. Die Ergebnisse wurden durch eine neue Verbindung erzielt, die die Autoren zwischen Einweg-Quantenkommunikationsprotokollen und semidefiniten Programmierumformulierungen von linearen Programmen herstellten.
[1] Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary and Ronald de Wolf: Exponential Lower Bounds for Polytopes in Combinatorial Optimization. STOC 2012: 95-106. J. ACM, 62(2), 17:1-17:23 (2015).
Der Gödel-Preis ist ein jährlich vergebener Preis für herausragende Arbeiten in der theoretischen Computerwissenschaft. Benannt ist er nach Kurt Gödel in Anerkennung seiner bedeutenden Beiträge zur mathematischen Logik und seines Interesses an der berühmten "P versus NP"-Frage. Der Preis wird von der European Association for Theoretical Computer Science (EATCS) und der Special Interest Group on Algorithms and Computation Theory (SIGACT) der Association for Computing Machinery (ACM) gesponsert und ist mit 5.000 USD dotiert.
Mehr Informationen:
