Efficient Preprocessing

Modulnummer: Q06-19
Englischer Titel: Efficient Preprocessing
Leistungspunkte: 6
Lehrperson: Kratsch

Empfohlene Vorkenntnisse

Solide Grundkenntnisse zu Algorithmen und Komplexität.

Zwingende Voraussetzungen

keine

Inhalt

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.

Erforderliche Arbeitsleistungen für LP-Vergabe und Prüfungszulassung

- schriftlich eingereichte und/oder mündlich vorgetragene Lösungen zu Aufgaben

Lehrveranstaltungen

Vorlesung: 3 SWS
Übung: 1 SWS

Zugeordneter Vertiefungsschwerpunkt

Algorithmen und Modelle: ja
Modellbasierte Systementwicklung: nein
Daten- und Wissensmanagement: nein
Ohne Vertiefungsschwerpunkt: nein

Sprache im Modul

Deutsch: nein
Englisch: ja

Angeboten für Studiengänge

M. Sc.: ja
M. Ed.: ja
Wirtschaftsmaster: ja

Angeboten im

Wintersemester: nein
Sommersemester: nein

Turnus

Alle zwei Jahre