Efficient preprocessing refers to the simplification of input instances before starting the actual computation for solving them. Usually the goal is to shrink the input without changing the result of solving it. This is especially useful in the case of NP-hard problems where algorithms may take exponential time to solve inputs, and where polynomial-time preprocessing may therefore greatly reduce the computational effort.Most of the lecture focuses on the notion of kernelization from parameterized complexity. We will learn how to design and analyze kernelization algorithms for NP-hard problems but also how to prove lower bounds for kernelization. We will also discuss relaxed variants of kernelization such as Turing kernelization and lossy kernelization. Further topics include preprocessing for tractable problems as well as preprocessing under uncertainty.
LV findet in Englisch statt.Den Einschreibeschlüssel zum Moodle-Kurs gibt es nach Abschluss der Platzvergabe durch AGNES per Email. Dies erfolgt ein bis zwei Tage nach Ende der Einschreibefrist bzw. Nachfrist.--The module is given in English.The key to the Moodle course will be sent via email after AGNES has finished the assignment process. This happens one or two days after the end of the enrollment time window.
Die Veranstaltung wurde 1 mal im Vorlesungsverzeichnis SoSe 2025 gefunden:
