Résolution exacte de problèmes NP-difficiles

ECTS : 3

Volume horaire : 15

Description du contenu de l'enseignement :

Most interesting optimization problems are NP-hard and therefore require exponential time to solve. Nevertheless, we often do need to solve them to optimality. The objective of this course is to study algorithms which, though taking exponential time in the worst case, are able to solve NP-hard problems while still offering good performance guarantees.

The main topic we will study is parameterized algorithms and complexity, which is the paradigm that leverages input structure to obtain algorithms with efficient running times. We will introduce the basic techniques of this algorithm design field, including bounded search trees, kernelization, color coding, and dynamic programming and show how these techniques can be applied via concrete examples of standard optimization problems (e.g. Vertex Cover, Coloring, Dominating Set, etc.). We will also discuss the corresponding complexity theory which traces the limits of these techniques.
 

Compétence à acquérir :

• Algorithms design technique for parameterized and exact algorithms.
• Technique to prove strong hardness for NP-hard problems.

Bibliographie, lectures recommandées :

Bibliographie

• M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized Algorithms. Springer, 2015.
• F. V. Fomin, D. Kratsch, Exact Exponential Algorithms, Springer-Verlag, 2010.