Paul Jünger, a 20-year-old Bachelor's student of computer science at the University of Bonn, and his team took first place in the “Exact Track” and third place in the Parameterized Track of the PACE Challenge 2024. At the International Symposium on Parameterized and Exact Computation IPEC 2024 in London at the beginning of September, the winner received the prize worth 400 euros. He then gave a presentation on his software solution, which is based on new techniques for the Linear Ordering Problem and the Feedback Arc Set Problem.
Every year, the Parameterized Algorithms and Computational Experiments (PACE) Challenge sets an algorithm problem from the fields of multivariate algorithms, exact algorithms, fine-grained complexity or related areas, which must be solved in the best possible way. Teams from all over the world can take part.
This year's task involved a difficult crossing minimization problem for which the participating teams had to develop their own algorithms. There were three tracks in total, each with a different focus for solving the task: one for exact algorithms for cases with “few” crossings (Exact Track), one for heuristic algorithms for instances that may require many crossings (Heuristic Track) and one for exact parameterized algorithms for instances with a small cut width (Parameterized Track). Jünger and his team took part in the Exact Track and the Parameterized Track.
All participating teams were able to test their programs on one hundred public problem instances. The submitted programs were independently tested by the organizers on these hundred and another hundred non-public instances. The main criterion in the Exact and Parameterized Track was how many instances could be optimally solved in thirty minutes of computation time. With 199 out of 200 instances solved in 5682 seconds, Jünger, as a junior member of his team, achieved the first place in the Exact Track and with 200 out of 200 instances solved in 25 seconds the third place in the Parameterized Track. The other team members were Prof. Dr. Petra Mutzel, head of the “Computational Analytics” working group at the Institute of Computer Science in Bonn, Prof. Dr. Michael Jünger (Cologne) and Prof. Dr. Gerhard Reinelt (Heidelberg).