2017/2018 Edition

Exact Algorithms for NP-hard Problems

Lecturer: Dr. Łukasz Kowalik (University of Warsaw).

Course summary: Many important computational problems turn out to be NP-hard and hence it is unlikely that they have polynomial time algorithms. However, this does not mean that progress is impossible. Most of the research in this area introduces some kind of a compromise: e.g. solving the problem efficiently in important special cases, finding a solution which does not need to be optimal but is provably close to optimal, etc.
In this mini-course we do not allow a compromise. We are interested in the worst-case complexity of NP-hard problems. This means we consider exponential-time algorithms. With the power of todays computers a O(2n)-time algorithm runs for several seconds when n is at most 30. This might be useful. But what if we can speed up the algorithm to O(1.4n)? Then we can consider instances of order n=60. And what if a O(1.01n)-time solution is possible?
It turns out that in many cases there are much better solutions than just do the exhaustive search. In this mini-course I will discuss several basic approaches, like branching, measure and conquer, divide and conquer, dynamic programming, fast matrix multiplication, inclusion-exclusion principle.

Slides

Assignment
Tasks are here: [PDF]. Due: 11th July (please send pdf to Lukasz).