The diameters of network-flow polytopes satisfy the Hirsch conjecture

DOI10.1007/s10107-017-1176-xzbMath1406.52023arXiv1603.00325OpenAlexW2963380173WikidataQ122904010 ScholiaQ122904010MaRDI QIDQ1785200

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

Publication date: 28 September 2018

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

simplex methodcombinatorial diameterHirsch conjecturenetwork simplex methodtransportation polytopesdiameter of graphs of polyhedranetwork-flow polytopes

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Linear programming (90C05) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Related Items

Formalizing the Face Lattice of Polyhedra, Monotone diameter of bisubmodular polyhedra, Adjacencies on random ordering polytopes and flow polytopes, On the Combinatorial Diameters of Parallel and Series Connections, A Friendly Smoothed Analysis of the Simplex Method, A note on the diameter of convex polytope, On Dantzig figures from graded lexicographic orders, On the Circuit Diameter of Some Combinatorial Polytopes, On the circuit diameter conjecture, Unnamed Item, On the Computation of Kantorovich--Wasserstein Distances Between Two-Dimensional Histograms by Uncapacitated Minimum Cost Flows, A note on the approximability of deepest-descent circuit steps, On the Length of Monotone Paths in Polyhedra

Uses Software

• LPbook

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the diameter of lattice polytopes
• On the diameter of partition polytopes and vertex-disjoint cycle cover
• A counterexample to the Hirsch conjecture
• An update on the Hirsch conjecture
• 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
• A polynomial time primal network simplex algorithm for minimum cost flows
• The hierarchy of circuit diameters and transportation polytopes
• The Hirsch conjecture is true for (0,1)-polytopes
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Four questions on Birkhoff polytopes
• The \(d\)-step conjecture for polyhedra of dimension \(d<6\)
• On the Assignment Polytope
• The Hirsch Conjecture for Dual Transportation Polyhedra
• Combinatorics and Geometry of Transportation Polytopes: An Update
• Diagnosing Infeasibility in Min-cast Network Flow Problems Part I: Dual Infeasibility
• A bad network problem for the simplex method and other minimum cost flow algorithms
• On sub-determinants and the diameter of polyhedra
• Linear programming. Foundations and extensions