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

dc.rights.license	CC-BY-NC-ND
dc.contributor.advisor	Dadush, D.N.
dc.contributor.advisor	Cornelissen, G.L.M.
dc.contributor.author	Huiberts, S.
dc.date.accessioned	2018-01-19T18:02:04Z
dc.date.available	2018-01-19T18:02:04Z
dc.date.issued	2018
dc.identifier.uri	https://studenttheses.uu.nl/handle/20.500.12932/28439
dc.description.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.
dc.description.sponsorship	Utrecht University
dc.format.extent	4195508
dc.format.mimetype	application/pdf
dc.language.iso	en_US
dc.title	How Large is the Shadow? Smoothed Analysis of the Simplex Method
dc.type.content	Master Thesis
dc.rights.accessrights	Open Access
dc.subject.keywords	Linear Programming, Shadow Vertex Simplex Method, Smoothed Analysis,
dc.subject.courseuu	Mathematical Sciences