Paul Jünger, ein 20-jähriger Bachelorstudent der Informatik an der Universität Bonn, hat in der PACE Challenge 2024 gemeinsam mit seinem Team den ersten Platz im Exact Track sowie den dritten Platz im Parameterized Track belegt. Auf dem International Symposium on Parameterized and Exact Computation IPEC 2024 Anfang September in London nahm der Gewinner den mit 400 Euro dotierten Preis entgegen. Im Anschluss hielt er einen Vortrag über seine Softwarelösung, die auf neuen Techniken für das Linear Ordering Problem bzw. das Feedback Arc Set Problem beruht.
Bei der Parameterized Algorithms and Computational Experiments (PACE) Challenge wird jedes Jahr ein Algorithmus-Problem aus den Bereichen multivariate Algorithmen, exakte Algorithmen, feinkörnige Komplexität oder verwandten Gebieten gestellt, das es bestmöglich zu lösen gilt. Teilnehmen können Teams aus aller Welt.
In der diesjährigen Aufgabe ging es um ein schwieriges Kreuzungsminimierungsproblem, für das die teilnehmenden Teams eigene Algorithmen entwickeln mussten. Dabei gab es insgesamt drei Tracks, die jeweils einen unterschiedlichen Fokus für die Lösung der Aufgabe hatten: einen für exakte Algorithmen für Fälle mit „wenigen“ Kreuzungen (Exact Track), einen für heuristische Algorithmen für Instanzen, die viele Kreuzungen erfordern können (Heuristic Track) und einen für exakte parametrisierte Algorithmen für Instanzen mit kleiner Schnittbreite (Parameterized Track). Jünger und sein Team nahmen im Exact und im Parameterized Track teil.
Alle teilnehmenden Teams konnten ihre Programme auf hundert öffentlichen Probleminstanzen testen. Die eingereichten Programme wurden von den Organisator*innen auf diesen hundert sowie weiteren hundert nichtöffentlichen Instanzen unabhängig getestet. Das Hauptkriterium im Exact und im Parameterized Track war es, wie viele Instanzen in dreißig Minuten Rechenzeit optimal gelöst werden konnten. Mit 199 von 200 gelösten Instanzen in 5682 Sekunden erreichte Jünger als Junior-Mitglied seines Teams den ersten Platz im Exact Track sowie mit 200 von 200 gelösten Instanzen in 25 Sekunden den dritten Platz im Parameterized Track. Die anderen Teammitglieder waren Prof. Dr. Petra Mutzel, Leiterin der Arbeitsgruppe "Computational Analytics" am Institut für Informatik Bonn, Prof. Dr. Michael Jünger (Köln) sowie Prof. Dr. Gerhard Reinelt (Heidelberg).