The Random Edge Simplex Algorithm on Dual Cyclic 4-Polytopes

MaRDI QIDQ6477126zbMATH OpenFDO

Authors Rafael Gillmann

Publication date 4 May 2006

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Randomized algorithms (68W20) Linear programming (90C05)

Abstract: The simplex algorithm using the random edge pivot-rule on any realization of a dual cyclic 4-polytope with n facets does not take more than O(n) pivot-steps. This even holds for general abstract objective functions (AOF) / acyclic unique sink orientations (AUSO). The methods can be used to show analogous results for products of two polygons. In contrast, we show that the random facet pivot-rule is slow on dual cyclic 4-polytopes, i.e. there are AUSOs on which random facet takes at least Omega(n^2) steps.

This page was built for publication: The Random Edge Simplex Algorithm on Dual Cyclic 4-Polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6477126)