April 19 – 24 , 2009, Dagstuhl Seminar 09171
Adaptive, Output Sensitive, Online and Parameterized Algorithms
For support, please contact
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 rst 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.
- 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