It is generally believed that NP-hard problems do not have polynomial time algorithms that solve them. Suppose we want to know the exact solution to an NP-hard problem: we then can look for algorithms that use exponential time, but that still are as fast as possible. In this seminar, we investigate a number of algorithmic techniques for exactly solving (NP-)hard problems, and for analysing algorithms that use exponential time. Amongst others, we look to branch-and-reduce, inclusion-exclusion, algorithms on planar graphs. We also investigate topics from fixed parameter tractability: suppose that we want to solve a problem exactly, but we know that there is a solution of small size. Does that help? And if so, how much? In the course, we look at a number of modern (and a few old) algorithms, but will also try to build and analyse fast exponential algorithms for a few specifically selected problems.

 

http://www.cs.uu.nl/education/vak.php?vak=INFOMSEAHP&jaar=2008