Abstract of Paper

Smoothed Analysis of Three Combinatorial Problems
by Cyril Banderier, Kurt Mehlhorn and Rene Beier

Abstract:

Smoothed analysis combines elements over worst-case and average case analysis. For 
an instance x the smoothed complexity is the average complexity of an instance obtained 
from x by a perturbation. The smoothed complexity of a problem is the worst smoothed 
complexity of any instance. Spielman and Teng introduced this notion for continuous 
problems. We apply the concept to combinatorial problems and study the smoothed 
complexity of three classical discrete problems: quicksort, left-to-right maxima counting, 
and shortest paths. This opens a vast field of nice analyses (using for example generating 
functions in the discrete case) which should lead to a better understanding of complexity 
landscapes of algorithms.