https://www.dagstuhl.de/08431

October 19 – 24 , 2008, Dagstuhl Seminar 08431

Moderately Exponential Time Algorithms

Organizers

Fedor V. Fomin (University of Bergen, NO)
Kazuo Iwama (Kyoto University, JP)
Dieter Kratsch (University of Metz, FR)

For support, please contact

Dagstuhl Service Team

Documents

Dagstuhl Seminar Proceedings DROPS
List of Participants

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.

Dagstuhl Seminar Series

Classification

  • Data Structures / Algorithms / Complexity

Keywords

  • Algorithms
  • Exponential time algorithms
  • SAT
  • Graphs

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.