Moderately Exponential Time Algorithms

Summary

The Dagstuhl seminar on Moderately Exponential Time Algorithms took place from 19.10.08 to 24.10.08. This was the first meeting of researchers working on exact and "fast exponential time" algorithms for hard problems. In total 54 participants came from 18 countries.

Moderately exponential time algorithms for NP-hard problems are a nat- ural type of algorithms and research on them dates back to Held and Karp's paper on the travelling salesman problem in the sixties. However until the year 2000, papers were published only sporadically (with the exception of work on satisfiability problems maybe). Some important and fundamental techniques have not been recognized at full value or even been forgotten, as e.g. the Inclusion-Exclusion method from Karp's ORL paper in 1982.

Recently the situation has changed — there is a rapidly increasing interest in exponential time algorithms and papers on various NP-hard problems have been accepted for high-level conferences in the last few years. As an impact of this interest we witnessed significant algorithmic breakthroughs for a set of fundamental problems. There are many (young) researchers that are attracted by moderately exponential time algorithms, and this interest is easy to explain, the field is still an unexplored continent with many open problems and new techniques are still to appear to solve such problems.

Despite of the growing interest and the new researchers joining the potential community there has not been a workshop on moderately exponential time algorithms longer than one day since the year 2000. The major goal of the proposed Dagstuhl seminar was to unite for one week many of the researchers being interested in the design and analysis of moderately exponential algorithms for NP-hard problems. The Dagstuhl seminar was a unique opportunity to bring together those people, to share insights and methods, present and discuss open problems and future directions of research in the young domain.

There were 27 talks and 2 open problem sessions. Talks were complemented by intensive informal discussions, and many new research directions and open problems will result from these discussions. The warm and encouraging Dagstuhl atmosphere stimulated new research projects. We expect many new research results and collaborations growing from the seeds of this meeting.