The hierarchy of circuit diameters and transportation polytopes

DOI10.1016/j.dam.2015.10.017zbMath1383.05072arXiv1411.1701OpenAlexW2210056327WikidataQ60242755 ScholiaQ60242755MaRDI QIDQ1707908

Jacob Miller, Jesús A. De Loera, Steffen Borgwardt, Elisabeth Finhold

Publication date: 4 April 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1411.1701

zbMATH Keywords

graph diametercircuit diameterHirsch conjecturetransportation polytopes

Mathematics Subject Classification ID

Linear programming (90C05) Distance in graphs (05C12)

Related Items

An implementation of steepest-descent augmentation for linear programs, Circuit walks in integral polyhedra, Edges versus circuits: a hierarchy of diameters in polyhedra, On the Circuit Diameter of Some Combinatorial Polytopes, Improved bounds on the diameter of lattice polytopes, On the circuit diameter conjecture, The diameters of network-flow polytopes satisfy the Hirsch conjecture, Factorized mutual information maximization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The circuit diameter of the Klee-Walkup polyhedron
• On the diameter of partition polytopes and vertex-disjoint cycle cover
• A counterexample to the Hirsch conjecture
• An update on the Hirsch conjecture
• Signature classes of transportation polytopes
• A linear bound on the diameter of the transportation polytope
• Graphs of transportation polytopes
• Many polytopes meeting the conjectured Hirsch bound
• More polytopes meeting the conjectured Hirsch bound
• Edges versus circuits: a hierarchy of diameters in polyhedra
• The Hirsch conjecture is true for (0,1)-polytopes
• Adjacency on combinatorial polyhedra
• On the Assignment Polytope
• The Hirsch Conjecture for Dual Transportation Polyhedra
• On the Circuit Diameter of Dual Transportation Polyhedra
• Combinatorics and Geometry of Transportation Polytopes: An Update
• The Multi-Index Problem