Computer Scientists have been challenged by the existence of remarkable algorithms that work well in practice, but whose theoretical analyses suggest that these algorithms should perform poorly or are inconclusive. The root of this problem is that traditional theoretical analyses measure the performance of algorithms on their worst inputs. This research analyzes the performance of algorithms using smoothed analysis, a new measure of the performance of algorithms that can better predict practical performance. Using smoothed analysis, this research aims to explain the good practical performance of some algorithms that are famous for outperforming pessimistic worst-case analyses.
In particular, algorithms that take real or complex inputs, such as those that usually occur in scientific and engineering applications, are examined under random perturbations of their worst-case inputs. The most famous of these, the simplex method for linear programming, was the subject of the paper introducing smoothed analysis. Yet, this work only investigated one rarely-used pivot rule. This research attempts smoothed analyses of the simplex method under more commonly used pivot rules. It also considers smoothed analyses of interior point methods and algorithms for convex programming. An attempt is being made to extend this analysis to algorithms that take discrete inputs.
