How Large is the Shadow? Smoothed Analysis of the Simplex Method

Abstract

In this thesis, we show a new improved upper bound on the expected number of edges in the shadow of a random smoothed polyhedron on a two-dimensional plane. We use this bound to give smoothed complexity bounds for the simplex method for linear programming based on existing algorithmic techniques.