TOP
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
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 00371

Experimental Algorithmics

( Sep 10 – Sep 15, 2000 )

Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/00371

Organizers
  • B. Moret (Albuquerque)
  • E. M. Schmidt (Aarhus)
  • R. Fleischer (Waterloo)





Summary

In recent years, many areas of theoretical computer science have experienced a shift to more applied research. Clear evidence of this fact is the surge of experimental papers in areas which used to be completely satisfied with a thorough theoretical analysis of the problems and algorithms. One reason for this is that people have learned that a purely theoretical analysis of an algorithm is often insufficient for practical purposes because

  • Many practical problems belong to "difficult'' problem classes (NP-complete problems or worse), so asymptotic worst-case bounds do not give a satisfactory answer to the question whether an algorithm is "useful'' or not.
  • More often then not, practical algorithms build on various heuristics where no tight bounds even exist.

So people have started to implement and test their algorithms besides of doing the usual theoretical analysis. Unfortunately, it is often not clear what these experiments actually tell us. Is an algorithm good just because it seems to behave well on random instances or on some benchmark test set? There is no sound basis for experimental algorithmics which could give us answers to questions like

  • What are relevant experiments?
  • What can be learned from experiments?
  • What is a good benchmark test set?

and finally

  • What is a good experimental paper?

The aim of this seminar was to bring together two groups, theoreticians and practitioners, to discuss these problems and start establishing a methodology of experimental algorithmics. In all, 45 researchers from 12 countries participated in the meeting. In all, 45 researchers with affiliations in Austria, Canada, Denmark, France, Germany, Great Britain, Greece, Hong Kong, Italy, the Netherlands, Spain, and the USA participated in the meeting. Three invited keynote speakers, Jon Bentley, David S. Johnson, and Kurt Mehlhorn, gave one-hour position talks. The remaining 26 presentations given by participants of the meeting covered a wide range of topics in experimental algorithmics. The abstracts of most of these presentations are contained in this seminar report. Two evenings were reserved for discussions on specific topics, a summary of the outcome of the discussions is included at the end of this report.

As usual, Schloss Dagstuhl proved to be an excellent place to hold a great meeting, so we would not only like to thank the participants of the seminar for making this a very successful event but also the Dagstuhl staff for providing a friendly and stimulating working environment.


Participants
  • B. Moret (Albuquerque)
  • E. M. Schmidt (Aarhus)
  • R. Fleischer (Waterloo)