Transportation Problems and Simplicial Polytopes That Are Not Weakly Vertex-Decomposable

DOI10.1287/moor.1120.0554zbMath1297.52002OpenAlexW2052513475MaRDI QIDQ2925352

Steven Klee, Jesús A. De Loera

Publication date: 21 October 2014

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/baaa19be60c490d87a1078598b325fd437187a7f

zbMATH Keywords

simplicial complexesconvex polytopesHirsch conjecturediameter of polyhedravertex-decomposability

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Computational aspects related to convexity (52B55) Linear programming (90C05) Combinatorial aspects of simplicial complexes (05E45) Combinatorial complexity of geometric structures (52C45)

Related Items

A Minimal Irreducible Triangulation of $$\mathbb{S}^{3}$$, Obstructions to weak decomposability for simplicial polytopes, Hirsch polytopes with exponentially long combinatorial segments, Recent progress on the combinatorial diameter of polytopes and simplicial complexes

Uses Software

• SageMath

Cites Work

• A counterexample to the Hirsch conjecture
• An update on the Hirsch conjecture
• A linear bound on the diameter of the transportation polytope
• An upper bound for the diameter of a polytope
• The many facets of linear programming
• The Hirsch Conjecture for Dual Transportation Polyhedra
• The d-Step Conjecture and Its Relatives
• Decompositions of Simplicial Complexes Related to Diameters of Convex Polyhedra
• A quasi-polynomial bound for the diameter\\of graphs of polyhedra
• The width of five-dimensional prismatoids