TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 08431

Moderately Exponential Time Algorithms

( Oct 19 – Oct 24, 2008 )

(Click in the middle of the image to enlarge)

Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/08431

Organizers

Contact


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.


Participants
  • Faisal N. Abu-Khzam (Lebanese American University, LB) [dblp]
  • Evgeny Dantsin (Roosevelt University - Chicago, US)
  • Bruno Escoffier (University Paris-Dauphine, FR)
  • Henning Fernau (Universität Trier, DE) [dblp]
  • Fedor V. Fomin (University of Bergen, NO) [dblp]
  • Martin Fürer (Pennsylvania State University - University Park, US) [dblp]
  • Serge Gaspers (University of Chile - Santiago de Chile, CL) [dblp]
  • Andreas Goerdt (TU Chemnitz, DE) [dblp]
  • Fabrizio Grandoni (University of Rome "Tor Vergata", IT) [dblp]
  • Pinar Heggernes (University of Bergen, NO) [dblp]
  • Edward A. Hirsch (Steklov Institute - St. Petersburg, RU) [dblp]
  • Thore Husfeldt (Lund University, SE) [dblp]
  • Kazuo Iwama (Kyoto University, JP) [dblp]
  • Iyad A. Kanj (DePaul University - Chicago, US) [dblp]
  • Petteri Kaski (University of Helsinki, FI) [dblp]
  • Eun Jung Kim (Royal Holloway University of London, GB) [dblp]
  • Joachim Kneis (RWTH Aachen, DE) [dblp]
  • Mikko Koivisto (University of Helsinki, FI) [dblp]
  • Lukasz Kowalik (University of Warsaw, PL) [dblp]
  • Dieter Kratsch (University of Metz, FR) [dblp]
  • Stefan Kratsch (MPI für Informatik - Saarbrücken, DE) [dblp]
  • Alexander S. Kulikov (Steklov Institute - St. Petersburg, RU) [dblp]
  • Oliver Kullmann (Swansea University, GB) [dblp]
  • Konstantin Kutzkov (LMU München, DE)
  • Michael A. Langston (University of Tennessee, US)
  • Mathieu Liedloff (University of Orleans, FR) [dblp]
  • Daniel Lokshtanov (University of Bergen, NO) [dblp]
  • Matthias Mnich (TU Eindhoven, NL) [dblp]
  • Yoshio Okamoto (Tokyo Institute of Technology, JP) [dblp]
  • Vangelis Paschos (University Paris-Dauphine, FR) [dblp]
  • Ramamohan Paturi (University of California - San Diego, US) [dblp]
  • Christophe Paul (University of Montpellier 2, FR) [dblp]
  • Daniel Paulusma (Durham University, GB) [dblp]
  • Daniel Raible (Universität Trier, DE)
  • Igor Razgon (University College Cork, IE) [dblp]
  • Mike Robson (University of Bordeaux, FR)
  • Peter Rossmanith (RWTH Aachen, DE) [dblp]
  • Jörg Rothe (Heinrich-Heine-Universität Düsseldorf, DE) [dblp]
  • Saket Saurabh (University of Bergen, NO) [dblp]
  • Uwe Schöning (Universität Ulm, DE) [dblp]
  • Igor A. Semaev (University of Bergen, NO)
  • Gregory B. Sorkin (IBM TJ Watson Research Center - Yorktown Heights, US) [dblp]
  • Ulrike Stege (University of Victoria, CA) [dblp]
  • Alexey Stepanov (University of Bergen, NO)
  • Suguru Tamaki (Kyoto University, JP) [dblp]
  • Jan Arne Telle (University of Bergen, NO) [dblp]
  • Patrick Traxler (ETH Zürich, CH)
  • Johan van Rooij (Utrecht University, NL) [dblp]
  • Virginia Vassilevska Williams (Institute of Advanced Study - Princeton, US) [dblp]
  • Yngve Villanger (University of Bergen, NO) [dblp]
  • Magnus Wahlström (MPI für Informatik - Saarbrücken, DE) [dblp]
  • Ryan Williams (IBM Almaden Center, US) [dblp]
  • Gerhard J. Woeginger (TU Eindhoven, NL) [dblp]
  • Ge Xia (Lafayette College - Easton, US) [dblp]

Related Seminars
  • Dagstuhl Seminar 10441: Exact Complexity of NP-hard Problems (2010-10-31 - 2010-11-05) (Details)
  • Dagstuhl Seminar 13331: Exponential Algorithms: Algorithms and Complexity Beyond Polynomial Time (2013-08-11 - 2013-08-16) (Details)

Classification
  • data structures / algorithms / complexity

Keywords
  • algorithms
  • exponential time algorithms
  • SAT
  • graphs