Exact Resolution of NP-hard problems

Spring 2019

[Announcements] [General Information] [Additional Material] [Schedule]


General Information

Course name: Exact Resolution of NP-hard Problems
Instructors: Michail Lampis and Eunjung Kim
Email: michail.lampis AT dauphine.fr and eunjungkim78 AT gmail.com

In this course we cover basic algorithmic techniques for dealing with problem that (probably) cannot be solved in polynomial time. We cover the basic toolbox of exponential-time algorithms, parameterized complexity, as well as the related hardness theories.

More information on the topics to be covered appears in the schedule below (which will be updated during the semester).

The course consists of 10 lectures of 1.5 hours

The final grades for the course will be based on homework assignments. There will be no exam.

Additional Material / Bibliography


Lecture No. Date Topic Notes
1 28/1 Branching Algorithms notes
2 30/1 Kernelization homework 2, notes
3 4/2 Randomized Algorithms homework 3, notes
4 6/2 Iterative Compression homework 4, notes
5 11/2 Inclusion-Exclusion homework 5
6 13/2 Exponential Time Hypothesis notes,
7 18/2 Parameterized Hardness notes,
8 20/2 More hardness Lec. 7 continued, homework 6 (with solution)
9 25/2 Structural Parameters/Treewidth/DP notes
10 27/2 Local Search