This year the topic of INF 339 is exact (exponential) algorithms for solving hard problems.
The seminal observations from the late 1960s that many common computational problems did not seem to have any efficient algorithm and could therefore not be solved in practice, has continued to guide the field of algorithms and computational complexity. How to deal with these seemingly intractable NP-hard problems?
It is now commonly believed that P$\neq$ NP and that there is no
polynomial time algorithms for the NP-hard problems. Several methods
for dealing with NP-hard optimization problems were developed
during the last 30 years including approximation, randomized and
online algorithms and heuristic methods. All these approaches have
drawbacks and disadvantages.
In this same period the hardware industry
has produced computers whose internal clock-rates are such that computational
efforts taking several hours some years ago are now dealt with in milliseconds.
With the increased speed of modern computers, certain
NP-hard problems can be solved effectively, and fast
algorithms, even though they have exponential running times in the worst case, may actually lead to
practical algorithms, at least for moderate instance sizes.
For example it is nowadays
routine to solve travelling salesman (TSP) instances with up to 2000 cities.
And if the data is nicely structured, then instances with up to 15,112 cities
can be handled in practice.
For practical purposes an algorithm with exponential running time $O(1.01^n)$ is usually
preferable over one with polynomial running time $O(n^4)$. The goal is to find the fastest
exponential algorithms for NP-hard problems.
The last few years has thus seen an emerging interest in
exact solutions for NP-hard problems.
Faster exact solutions for NP-hard problems are sought out not only for their own sake,
but also in order to gain insights into complexity.
This is a hot topic in algorithms research combining ideas from AI (constraint programming and large-scale search for solutions of NP-hard problems) with theoretical computer science (worst case analysis and algorithmic improvement). There is also plenty of room for new research due to the large gap between experimentally measured performance and known worst case bounds.
There remain many open problems and challenging questions around the
worst case analysis of exact algorithms for NP-hard problems. This seems to be
a rich and promising area. We only have a handful of techniques available, and
there is ample space for improvements and for new results.
There is no assigned text, due to the novelty of the subject area.
In general we shall try to follow Gerhard Woeginger's survey
Exact algorithms for NP-hard problems.
Also there will be a set of papers to read over the course.
The format will be lecture and discussion, with a small amount of homework.
A strong understanding of analysis of algorithms, at least at the
INF 334 level is recommended.
The first lecture: 23/01, at 10.15 in Grupperom 2104, Hoyteknologisenteret