Processing...

**
We describe constructions of extended formulations that establish a certain relaxed version of the Hirsch-conjecture. Those constructions can be used to show that if there is a pivot rule (executable by a strongly polynomial time algorithm) for the simplex algorithm for which one can bound the number of steps by the diameters of the bases-exchange graphs of the polyhedra of feasible solutions then the general linear programming problem can be solved in strongly polynomial time. The talk is based on joint work with Kirill Kukharenko.
**

G. Stauffer

Visibility:

archived