Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time

Abstract

We introduce the smoothed analysis of algorithms, which is a hybrid of the worst-case and average-case analysis of algorithms. In smoothed analysis, we measure the maximum over inputs of the expected performance of an algorithm under small random perturbations of that input. We measure this performance in terms of both the input size and the magnitude of the perturbations. We show that the simplex algorithm has polynomial smoothed complexity.

Revised. Improved statement of main theorem

Cited by in corpus (5)

• Universal discriminative quantum neural networks
• Cycles and matchings in randomly perturbed digraphs and hypergraphs
• Fast Algorithms for Rank-1 Bimatrix Games
• From acquaintance to best friend forever: robust and fine-grained inference of social tie strengths
• A Novel Skip Orthogonal List for Dynamic Optimal Transport Problem