Smoothed analysis of three combinatorial problems

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 eld of nice analyses (using for example generating functions in the discrete case) which should lead to a better understanding of complexity landscapes of algorithms.