April 19 – 24 , 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)

For support, please contact

Dagstuhl Service Team


Dagstuhl Seminar Proceedings DROPS
List of Participants


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 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).

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.


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