19. – 24. April 2009, Dagstuhl-Seminar 09171

Adaptive, Output Sensitive, Online and Parameterized Algorithms


Jérémy Barbay (University of Chile – Santiago de Chile, CL)
Rolf Klein (Universität Bonn, DE)
Alejandro Lopez-Ortiz (University of Waterloo, CA)
Rolf Niedermeier (Universität Jena, DE)

Auskunft zu diesem Dagstuhl-Seminar erteilt

Dagstuhl Service Team


Dagstuhl Seminar Proceedings DROPS


Traditionally the analysis of algorithms measures the complexity of a problem or algorithm in terms of the worst-case behavior over all inputs of a given size. However, in certain cases an improved algorithm can be obtained by considering a finer partition of the input space. For instance, it has been observed that in certain applications, sequences to be sorted are nearly in sorted order. In this setting one would expect that such sequences should be sorted in less time than a perfectly shuffled sequence. An adaptive sorting algorithm takes advantage of existing order in the input, with its running time being a function of the disorder in the input.

The workshop was organized into a serie of tutorials and "bridging" talks in the first two days, followed by a three days of more regular taks grouped by pairs of themes, with a large amount of time left for interaction in the afternoon, and two "exchange sessions" on Tuesday and Wednesday evenings.

The workshop succeeded in attracting many young students, and a proportion of female participants larger than usual in computer science. The survey attests in particular that the workshop suggested new directions of research (22 participants rated the sentence "The seminar identified new research directions." on average of 4.05 out of 5), but that participants would prefer to receive the schedule of the workshop earlier.

During the exchange sessions, many participants mentionned that they enjoyed from hearing about proof techniques and open problems in areas they were not familiar with before. After the session, several participants, both young and more experienced, contacted the organizers separately to express their satisfaction with the social aspect of the seminar.

Related Dagstuhl-Seminar


  • Computer Graphics / Computer Vision
  • Data Bases / Information Retrieval
  • Data Structures / Algorithms / Complexity
  • Optimization / Scheduling


  • Adaptive analysis
  • Instance optimal algoritms
  • Fixed parameter tractable
  • Output sensitive algorithms


In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.


Download Übersichtsflyer (PDF).

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.


Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.