Exact Resolution of NP-hard problems

Spring 2016

[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 29/1 Branching Algorithms homework 1
2 1/2 Iterative Compression homework 2
3 2/2 Kernelization notes
4 3/2 Kernelization II notes
5 4/2 Color Coding notes,homework 3
6 8/2 Exponential Time Hypothesis notes, homework 4
7 12/2 Parameterized Hardness notes,homework 5
8 15/2 More hardness Lec. 7 continued
9 18/2 Structural Parameters/Treewidth/DP notes
10 19/2 Local Search homework 6