Parameterized Algorithms Dániel Marx

Registration for this course is open until Monday, 18.10.2021 23:59.

News

Currently, no news are available
 

Parameterized Algorithms

This course is about designing fast algorithms for NP-hard graph theoretic problems, where the running time depends on multiple parameters of the input. For example, while a database may contain a very large amount of data, the size of the database queries is typically extremely small in comparison. The aim would be to obtain algorithms that have a small dependence on the database size, but possibly a larger dependence on the query size. Such an algorithm would be fast when the queries are small.

We will see several algorithmic techniques to design fast algorithms for NP-hard problems in this setting, called Fixed Parameter Tractable (FPT) algorithms, as well as an overview of the lower-bound methods. We will also learn about preprocessing or data-reduction algorithms in this setting, called Kernelization algorithms, which run in polynomial time and reduce a given instance of a NP-hard problem to an equivalent but much smaller instance.

 

Format

Two hours of lectures every week and two hours of tutorials every other week.

Prerequisites

Basic knowledge of algorithms, graph theory and probability will be assumed.

 

 

 

 



Privacy Policy | Legal Notice
If you encounter technical problems, please contact the administrators