The simplex algorithm has polynomial smoothed complexity

You need to know: The notion of an algorithm and its complexity (number of steps it needs to solve a problem),  basic probability theory (expectation, standard deviation, Gaussian random variable), linear programming problem, simplex algorithm.

Background: Let A be an algorithm which solves some problem whose input is a vector in for some m, with norm . Let be the number of steps A works at input . The worst-case complexity of A is , where is the set of all possible inputs of bit-length n. The smoothed complexity of A is , where is a vector of Gaussian random variables of mean and standard deviation , and is the corresponding expectation. We say that an algorithm A has polynomial smoothed complexity if is bounded by a polynomial in n and .

The Theorem: On 19th November 2001, Daniel Spielman and Shang-Hua Teng submitted to arxiv a paper in which they introduced the notion of smoothed complexity and proved that simplex algorithm for linear programming problem has polynomial smoothed complexity.

Short context: The performance of algorithms are usually measured by their worst-case complexity. However, there are algorithms whose worst-case complexity grows exponentially fast, but which work fast for all inputs arising in practice. A prominent example of such an algorithm is the simplex method for linear programming problem. Spielman and Teng introduced smoothed complexity to measure worst-case expected performance of an algorithm under small random perturbations of its input. Because in practise input data are often subject to random noise, the Theorem provides theoretical explanation of good practical performance of the simplex method.

Links: Free arxiv version of the original paper is here, journal version is here.

Go to the list of all theorems