Carnegie Mellon University
file.pdf (280.91 kB)
Download file

Smoothed Analysis of the Perceptron Algorithm for Linear Programming

Download (280.91 kB)
journal contribution
posted on 1965-01-01, 00:00 authored by Avrim Blum, John Dunagan
The smoothed complexity [1] 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.


Publisher Statement

All Rights Reserved



Usage metrics