People: Prof. Dr. Tobias Friedrich, Dr. Kirill Simonov, Aikaterini Niklavotis, Dr. Sarel Cohen
Links: Lehrveranstaltungen IT-Systems Engineering, Algorithm Engineering Moodle

UPD 16.10: It is now possible to enroll in the course on Moodle.

As the name suggests, we plan to form a team that takes part in the 2024 PACE Challenge. This competition is held every year by the Parameterized Algorithms community, and the task is always to create practically efficient algorithms for an NP-hard (usually graph) problem. The problem of the 2024 challenge is to solve One-Sided Crossing Minimization: Given a bipartite graph with a fixed order of vertices on one side, what is the optimal ordering of the other side that minimizes the resulting number of crossings? (See also an illustration at the bottom.) Since there are exponentially many options for the desired ordering, it is not surprising that the problem is NP-hard. On the other hand, the problem has important applications, for example to minimize wire crossings in integrated circuit design. The challenge consists of the Exact track, where the task is to devise a solver that always returns an optimal solution, as well as the Heuristic track, where the solution is not required to be optimal, but smaller solutions yield higher score for the solver. The two tracks are ranked seperately.

The main motivation behind PACE contest is to develop new algorithmic approaches for a notoriously hard problem over many months. Aiming for exact solutions will require theoretical proof that the solver works correctly. A good PACE participation is therefore usually followed by a scientific publication about the theoretical properties discovered while working towards the contest. However, efficient implementation of the solver is also important, since the resulting running time is part of the scoring; also, good architectural design of the solver makes it much easier to try new ideas and augment the solver's behaviour. Therefore, participation in the challenge requires both theoretical analysis and algorithm engineering — ad each participant of the course is free to choose on which aspect to focus, as part of the team. 

The submission of the final solver is in June 2024, and we plan to offer a second project seminar in Summer Semester 2024 as a continuation of this one. However, it is not mandatory to join both courses; each semester is graded separately.

The initial few weeks of the current course will be about surveying the existing literature related to the problem and presenting the findings for the whole team. Then, we will aim to start with our first implemenation for the challenge. At the end of the semester you will be required to submit a writeup describing the current state of the implementation(s), the bottlenecks faced, and potential further ideas to strengthen the implementation(s).

We were successfull in PACE challenge 2022 by securing third place in the exact track, so let us restore the tradition!

We will meet once every week. We will also have a dedicated slack channel for the course for further communication. We can switch between in-person (with hybrid options) and zoom meetings as required. For example for the initial reading and presentation, it might be better to have in-person meetings.

We will have our first meeting on Monday, October 16 at 9:15-10:45 in K-1.02 with an option to join virtually via Zoom.
The technical data for the meeting will be published on Moodle.

There are no formal requirements. We expect some coding skills and at least a basic understanding of graphs and algorithms.

The grading for the course will be based on the presentations during the reading phase (30%), state of the implementation at the end of the semester (50%), and the writeup (20%).