Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Within this website:
External resources:
Within this website:
External resources:
  • the dblp Computer Science Bibliography

Dagstuhl Seminar 9626

On-line Algorithms

( Jun 24 – Jun 28, 1996 )

Please use the following short url to reference this page:

  • A. Fiat
  • G. Woeginger


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.


  • A. Fiat
  • G. Woeginger

Related Seminars
  • Dagstuhl Seminar 02271: Online Algorithms (2002-06-30 - 2002-07-05) (Details)