Dozent: Prof. Dr. Tobias Friedrich, Dr. Kirill Simonov, Dr. Shaily Verma, Dr. Sarel Cohen, Aikaterini Niklanovits
Links: Lehrveranstaltungen IT-Systems Engineering, Algorithm Engineering 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 — and each participant of the course is free to choose on which aspect to focus, as part of the team. 

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

The challenge is ongoing since autumn, and the participants of the previous semester's seminar have already made progress and developed some parts of the solver. It is up to this semester's team to add new, potentially more efficient methods to the solver, set up the execution pipeline that works the best on the publicly available instances, and optimize the performance of the solver.

The solver submission deadline is already in June, therefore the work on the codebase will be mostly concetrated in the first half of the semester. The second half of the semester will be dedicated to documenting the results of the project — PACE requires to submit additionally a solver description in the form of a short article. Moreover, after the competition we intend to submit the results to an appropriate scientific conference; turning the solver description into a proper research paper will thus be the second part of the project.

There are no formal requirements. Since we aim to take part in the programming competition and submit the corresponding publication, we expect some coding and scientific writing skills.

We welcome participants of the previous semester's PACE seminar, as well as new participants.

The evaluation of the course is based on the contribution towards the solver codebase, and the contribution to the scientific report in the second half of the semester. The code constitutes 50% of the grade, and the report 50% as well.

We meet weekly on Wednesday, 17:00-18:30, in K-2.04. First meeting takes place on April 10. We will switch between in-person (with hybrid options) and zoom meetings as required. There is also a dedicated slack channel for the course for further communication.