ALCOMFT-TR-02-21

Cyril Banderier, Kurt Mehlhorn and Rene Beier
Average case analysis of three combinatorial algorithms under limited randomness
INRIA and MPI. Work package 4. May 2002.

Abstract: We perform an average case case analysis of three classical algorithms under limited randomness: left-to-right maxima counting, quicksort and shortest paths. This kind of analysis have been introduced by Spielman & al. (under the name ``smoothed analysis'') for continuous problems. The idea is to average not over the complete space of instances but only over the instances which are obtained from a fixed input by a perturbation.

Postscript file: ALCOMFT-TR-02-21.ps.gz (95 kb).