Transportation problems and simplicial polytopes that are not weakly vertex-decomposable

DOI10.1287/MOOR.1120.0554MaRDI QIDQ2925352zbMATH OpenOpenAlexFDO

Authors Jesús A. De Loera, Steven Klee

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

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

Recommendations

• scientific article; zbMATH DE number 3904323
• scientific article; zbMATH DE number 3861931
• scientific article; zbMATH DE number 4172739
• Topics of polyhedral combinatorics in transportation problems with exclusions
• scientific article; zbMATH DE number 4070641
• Combinatorics and geometry of transportation polytopes: an update
• Polyhedral combinatorics of multi-index axial transportation problems
• Multi-index planar transportation polytopes with maximum number of vertices
• On the noninteger polyhedron vertices of the three-index axial transportation problem
• scientific article; zbMATH DE number 1294379

Cites work

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

Cited in

(7)

• Recent progress on the combinatorial diameter of polytopes and simplicial complexes
• Obstructions to weak decomposability for simplicial polytopes
• Posets arising as 1-skeleta of simple polytopes, the nonrevisiting path conjecture, and poset topology
• Hirsch polytopes with exponentially long combinatorial segments
• Not all simplicial polytopes are weakly vertex-decomposable
• A minimal irreducible triangulation of \(\mathbb S^3\)
• Topics of polyhedral combinatorics in transportation problems with exclusions

Describes a project that uses

Uses Software

• SageMath

This page was built for publication: Transportation problems and simplicial polytopes that are not weakly vertex-decomposable

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