On the facet pivot simplex method for linear programming II: a linear iteration bound

MaRDI QIDQ6387286zbMATH OpenFDO

Authors Ya-Guang Yang

Publication date 1 January 2022

Abstract: The Hirsch Conjecture stated that any $d$-dimensional polytope with n facets has a diameter at most equal to $n-d$. This conjecture was disproved by Santos (A counterexample to the Hirsch Conjecture, Annals of Mathematics, 172(1) 383-412, 2012). The implication of Santos' work is that all {it vertex} pivot algorithms cannot solve the linear programming problem in the worst case in $n-d$ vertex pivot iterations. In the first part of this series of papers, we proposed a {it facet} pivot method. In this paper, we show that the proposed facet pivot method can solve the canonical linear programming problem in the worst case in at most $n-d$ facet pivot iterations. This work was inspired by Smale's Problem 9 (Mathematical problems for the next century, In Arnold, V. I.; Atiyah, M.; Lax, P.; Mazur, B. Mathematics: frontiers and perspectives, American Mathematical Society, 271-294, 1999).

This page was built for publication: On the facet pivot simplex method for linear programming II: a linear iteration bound

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