Springe zum Hauptinhalt
Fakultät für Informatik

162. Informatik-Kolloquium


Herr Prof. Dr. Dieter Kratsch

Laboratoire dÌnformatique Théorique et Appliquée
Université de Metz

"Exact Exponential Algorithms"

Montag, 25.10.2010
15:00 Uhr, 1/336

Alle interessierten Personen sind herzlich eingeladen!


Today most computer scientists believe that NP-hard problems cannot be solved by polynomial time algorithms. From the polynomial-time perspective all NP-complete problems are equivalent but their exponential-time properties vary widely. Why do some NP-hard problems seem to be easier than others? What are the algorithmic techniques for solving hard problems significantly faster than the exhaustive brute-force search, trying all possible solutions? The algorithms addressing these questions are known as exact exponential algorithms.

The history of exact exponential algorithms for NP-hard problems dates back to the 1960s. Two classical examples are Bellman, Held and Karp’s dynamic programming algorithm for the Traveling Salesman problem and Ryser’s inclusion–exclusion formula for the permanent. The design and analysis of exact algorithms leads to a better understanding of hard problems and initiates interesting new combinatorial and algorithmic challenges. The last decade has witnessed a rapid development of the area, with many new algorithmic techniques discovered. This has transformed exact algorithms into a very active research field. This talk provides an introduction to the area and explains some of the fundamental algorithmic techniques.