## 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**

- 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).