UiB : MatNat : Informatikk : Undervisning


INF339 - Utvalgte emner i algoritmer og kompleksitet (Advanced Topics in Algorithms and Complexity)


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 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. (David Eppstein)

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

Papers:


The first lecture: 23/01, at 10.15 in Grupperom 2104, Hoyteknologisenteret