Parameterized algorithms are an approach for coping with the intractability of NP-hard computational problems. The central idea therein is to quantify the structure of input instances by one or more parameters. Then, one seeks algorithms that provably perform well when the chosen parameters are sufficiently small. In this way, we can formalize the intuition that typical instances may have plenty of useful structure, which distinguishes them from the worst case.There is a rich toolbox of algorithmic techniques that will be covered in the lecture. These include branching algorithms, kernelization, iterative compression, color coding, dynamic programming on tree decompositions, inclusion-exclusion, and others. The algorithmic techniques are complemented by lower bound methods that allow to rule out fast parameterized algorithms or that prove optimality of certain running times under appropriate assumptions.
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 2024 gefunden:
