Smoothed Analysis of the Perceptron Algorithm for Linear Programming
journal contributionposted on 01.01.1965, 00:00 by Avrim Blum, John Dunagan
The smoothed complexity  of an algorithm is the expected running time of the algorithm on an arbitrary instance under a random perturbation. It was shown recently that the simplex algorithm has polynomial smoothed complexity. We show that a simple greedy algorithm for linear programming, the perceptron algorithm, also has polynomial smoothed complexity, in a high probability sense; that is, the running time is polynomial with high probability over the random perturbation.