Rock extensions with linear diameters (Q6654117)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Rock extensions with linear diameters |
scientific article; zbMATH DE number 7959404
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Rock extensions with linear diameters |
scientific article; zbMATH DE number 7959404 |
Statements
Rock extensions with linear diameters (English)
0 references
18 December 2024
0 references
New constructions that lead to a certain relaxed version of the Hirsch conjecture are proposed. They allow proving that the general linear programming problem can be solved in strongly polynomial time if there is a pivot rule for the simplex algorithm for which one can bound the number of steps by a polynomial in the diameter plus the number of facets of the polyhedron of feasible optimal solutions.
0 references
Hirsch conjecture
0 references
polytope diameter
0 references
extended formulation
0 references
linear programming
0 references
