Experimental Algorithmics

Conference Proceedings LNCS 2547

Now available online. You can find it at the URL http://link.springer.de/link/service/series/0558/tocs/t2547.htm or http://link.springer-ny.com/link/service/series/0558/tocs/t2547.htm

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.