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
-time algorithm runs for several seconds when is at most .
This might be useful. But what if we can speed up the algorithm to
- March lectures (branching, measure and conquer, dynamic programming, divide and conquer): [PDF]
- May lectures (inclusion-exclusion, zeta and Moebius transforms, fast matrix multiplication, local search): [PDF]
Assignment
Tasks are here: [PDF].
Due: 11th July (please send pdf to Lukasz).