arXiv:2307.05246 Abstract | arXiv Analytics

arXiv:2307.05246 [math.CO]Abstract References Reviews Resources

Polytope Extensions with Linear Diameters

Published 2023-07-11Version 1

We describe constructions of extended formulations that establish a certain relaxed version of the Hirsch-conjecture and prove that if there is a pivot rule for the simplex algorithm for which one can bound the number of steps by the (monotone) diameter of the polyhedron of feasible solutions then the general linear programming problem can be solved in strongly polynomial time.

Categories: math.CO

Subjects: 52Bxx, 90C05

Keywords: polytope extensions, linear diameters, general linear programming problem, simplex algorithm, pivot rule

Related articles: Most relevant | Search more

arXiv:math/0309351 [math.CO] (Published 2003-09-22, updated 2004-08-20)

The Simplex Algorithm in Dimension Three

Volker Kaibel, Rafael Mechtel, Micha Sharir, Guenter M. Ziegler

arXiv:1308.0454 [math.CO] (Published 2013-08-02, updated 2014-12-21)

Tropicalizing the simplex algorithm

Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert, Michael Joswig

arXiv:math/0301076 [math.CO] (Published 2003-01-09)

The Random Edge Rule on Three-Dimensional Linear Programs