This workshop focusses on the analysis of algorithms in the {\em average case}, assuming a probabilistic distribution on input instances. The goal is to obtain good estimates of various performance measures of algorithms such as solution quality and running time. The main objective is to explain why many simple algorithms, often used in practice, perform much better than as predicted by worst-case analysis. Pathological cases are generally rare and simple algorithms can often be shown to perform well in the average case. This is especially true in the case of NP-complete problems where it seems that the probabilistic approach may be the best way and indeed may be the only way to understand the success of heuristic combinatorial algorithms.
We identify five major sub-areas as the focus of the workshop.
The workshop will bring together leading researchers in the Analysis of Algorithms along with younger researchers in the area. There should be about 15-20 lectures presenting progress, trends and open problems together with ample time for discussion. We believe that bringing together researchers from these different but closely related areas will result in an interesting cross-fertilisation of ideas.
Next: Call for Participation
Index
DIMACS Homepage