How Large is the Shadow? Smoothed Analysis of the Simplex Method
MetadataShow full item record
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.