UiB
:
MatNat
:
Informatikk
:
Undervisning
 
Course Description:
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 NPhard problems?
It is now commonly believed that P$\neq$ NP and that there is no
polynomial time algorithms for the NPhard problems. Several methods
for dealing with NPhard 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 clockrates 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
NPhard 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 NPhard problems.
The last few years has thus seen an emerging interest in
exact solutions for NPhard problems.
Faster exact solutions for NPhard 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 largescale search for solutions of NPhard 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.
(David Eppstein)
There remain many open problems and challenging questions around the
worst case analysis of exact algorithms for NPhard 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.
(Gerhard Woeginger)
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 NPhard 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.
Papers:
The first lecture: 23/01, at 10.15 in Grupperom 2104, Hoyteknologisenteret
