Dagstuhl Seminar 09171
Adaptive, Output Sensitive, Online and Parameterized Algorithms
( Apr 19 – Apr 24, 2009 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/09171
Organizers
- 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)
Contact
- Annette Beyer (for administrative matters)
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.
- Spyros Angelopoulos (MPI für Informatik - Saarbrücken, DE) [dblp]
- Jérémy Barbay (University of Chile - Santiago de Chile, CL) [dblp]
- Shai Ben-David (University of Waterloo, CA) [dblp]
- Sagi Ben-Moshe (Technion - Haifa, IL)
- Nadja Betzler (Universität Jena, DE)
- Joan Boyar (University of Southern Denmark - Odense, DK)
- Luca Castelli Aleardi (Ecole Polytechnique - Palaiseau, FR) [dblp]
- Marek Chrobak (University of California - Riverside, US) [dblp]
- Britta Dorn (Universität Tübingen, DE) [dblp]
- Reza Dorrigiv (University of Waterloo, CA) [dblp]
- Martin R. Ehmsen (University of Southern Denmark - Odense, DK)
- Amr Elmasry (MPI für Informatik - Saarbrücken, DE) [dblp]
- Leah Epstein (Haifa University, IL)
- Vladimir Estivill-Castro (Griffith University - Brisbane, AU)
- Lene Monrad Favrholdt (University of Southern Denmark - Odense, DK)
- Michael R. Fellows (University of Newcastle, AU) [dblp]
- Rudolf Fleischer (Fudan University - Shanghai, CN) [dblp]
- Robert Fraser (University of Waterloo, CA)
- Magdalena Grüber (HU Berlin, DE)
- Jiong Guo (Universität Jena, DE) [dblp]
- Marek Karpinski (Universität Bonn, DE) [dblp]
- David G. Kirkpatrick (University of British Columbia - Vancouver, CA) [dblp]
- Rolf Klein (Universität Bonn, DE) [dblp]
- Christian Knauer (FU Berlin, DE) [dblp]
- Stefan Kratsch (MPI für Informatik - Saarbrücken, DE) [dblp]
- Alexander Johannes Langer (RWTH Aachen, DE)
- Kim Skak Larsen (University of Southern Denmark - Odense, DK)
- Daniel Lokshtanov (University of Bergen, NO) [dblp]
- Alejandro Lopez-Ortiz (University of Waterloo, CA) [dblp]
- Dániel Marx (Budapest University of Technology & Economics, HU) [dblp]
- Nicole Megow (MPI für Informatik - Saarbrücken, DE) [dblp]
- Kurt Mehlhorn (MPI für Informatik - Saarbrücken, DE) [dblp]
- Friedhelm Meyer auf der Heide (Universität Paderborn, DE) [dblp]
- Ian Munro (University of Waterloo, CA) [dblp]
- Rolf Niedermeier (Universität Jena, DE) [dblp]
- Yoshio Okamoto (Tokyo Institute of Technology, JP) [dblp]
- Daniel Raible (Universität Trier, DE)
- Rüdiger Reischuk (Universität Lübeck, DE) [dblp]
- Frances A. Rosamond (University of Newcastle, AU) [dblp]
- Saket Saurabh (University of Bergen, NO) [dblp]
- Raimund Seidel (Universität des Saarlandes, DE) [dblp]
- Hadas Shachnai (Technion - Haifa, IL) [dblp]
- Ulrike Stege (University of Victoria, CA) [dblp]
- Gerhard J. Woeginger (TU Eindhoven, NL) [dblp]
- Sandra Zilles (University of Alberta - Edmonton, CA) [dblp]
Related Seminars
- Dagstuhl Seminar 18281: Synergies between Adaptive Analysis of Algorithms, Parameterized Complexity, Compressed Data Structures and Compressed Indices (2018-07-08 - 2018-07-13) (Details)
Classification
- computer graphics / computer vision
- data bases / information retrieval
- data structures / algorithms / complexity
- optimization / scheduling
Keywords
- adaptive analysis
- instance optimal algoritms
- fixed parameter tractable
- output sensitive algorithms
