The Dagstuhl meeting on On-line Algorithms brought together 55 researchers with affiliations in Argentina (1), Austria (1), Canada (2), Czechia (1), Germany (4), Hungary (2), Israel (7), Italy (3), the Netherlands (5) and the USA (29). 34 presentations were given: There were 16 survey talks presented by

• Daniel Sleator (On the history of on-line algorithms)
• Avrim Blum (On-line algorithms in machine learning)
• Sandy Irani (Paging problems)
• Christos Papadimitriou (Non-standard models for competitive analysis)
• Susanne Albers and Jeffery Westbrook (Self-organizing data-structures)
• Serge Plotkin (On-line routing problems)
• Bala Kalyanasundaram and Kirk Pruhs (On-line problems in networks)
• David Johnson (On-line bin packing)
• Lawrence Larmore and Marek Chrobak (Metrical task systems and the k-server problem)
• Anna Karlin (Competitive analysis in practice)
• James Aspnes (Competitive analysis of distributed algorithms)
• Yossi Azar (On-line load balancing)
• Hal Kierstead (On-line graph coloring)
• Ran El-Yaniv (Decision-theoretic foundations of competitive analysis)
• Jiří Sgall (On-line scheduling)
• Yair Bartal (On-line distributed paging)

Moreover there were 18 shorter contributions that presented recent results. The abstracts of all these presentations are contained in this seminar report in alphabetical order. Moreover, there is a list of with some open problems that were mentioned in the open problem session.

The organizers enjoyed the social aspects of the meeting, especially the alcohol. We had a wine-and-cheese party every evening; on Tuesday evening the party included an open problem session organized by David Johnson. On Thursday evening we had wine-and-cheese along with a panel discussion chaired by Danny Sleator on “The Future of Competitive Analysis”. Giorgio Ausiello and Alberto Marchetti-Spaccamela also discussed their plan to have yet another workshop on on-line algorithms in two years time, to be held in Sicily. On Wednesday evening, Kirk Pruhs organized an excursion to a pub in the nearby village where we watched the semi-finals of the European Soccer Championship.

Creative Commons BY 3.0 Unported license