June 24 – 28 , 1996, Dagstuhl Seminar 9626

On-line Algorithms


A. Fiat, G. Woeginger

For support, please contact

Dagstuhl Service Team


Dagstuhl's Impact: Documents available
Dagstuhl-Seminar-Report 149


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.

Related Dagstuhl Seminar


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.