The hierarchy of circuit diameters and transportation polytopes

DOI10.1016/J.DAM.2015.10.017zbMATH Open1383.05072DBLPjournals/dam/BorgwardtLFM18OpenAlexW2210056327WikidataQ60242755 ScholiaQ60242755MaRDI QIDQ1707908FDOQ1707908

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

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)

Abstract: The study of the diameter of the graph of polyhedra is a classical problem in the theory of linear programming. While transportation polytopes are at the core of operations research and statistics it is still open whether the Hirsch conjecture is true for general $mimesn$--transportation polytopes. In earlier work the first three authors introduced a hierarchy of variations to the notion of graph diameter in polyhedra. The key reason was that this hierarchy provides some interesting lower bounds for the usual graph diameter. This paper has three contributions: First, we compare the hierarchy of diameters for the $mimesn$--transportation polytopes. We show that the Hirsch conjecture bound of $m+n-1$ is actually valid in most of these diameter notions. Second, we prove that for $3imesn$--transportation polytopes the Hirsch conjecture holds in the classical graph diameter. Third, we show for $2imesn$--transportation polytopes that the stronger monotone Hirsch conjecture holds and improve earlier bounds on the graph diameter.

Recommendations

• On the circuit diameter of dual transportation polyhedra
• The diameters of network-flow polytopes satisfy the Hirsch conjecture
• Edges versus circuits: a hierarchy of diameters in polyhedra
• An O(\(n\)) bound for the diameter of transshipment polytopes
• scientific article; zbMATH DE number 3845342

Cites Work

• scientific article; zbMATH DE number 3828715 (Why is no real title available?)
• scientific article; zbMATH DE number 3177183 (Why is no real title available?)
• scientific article; zbMATH DE number 3294139 (Why is no real title available?)
• A counterexample to the Hirsch conjecture
• A linear bound on the diameter of the transportation polytope
• Adjacency on combinatorial polyhedra
• An update on the Hirsch conjecture
• Combinatorics and geometry of transportation polytopes: an update
• Edges versus circuits: a hierarchy of diameters in polyhedra
• Graphs of transportation polytopes
• Many polytopes meeting the conjectured Hirsch bound
• More polytopes meeting the conjectured Hirsch bound
• On the Assignment Polytope
• On the circuit diameter of dual transportation polyhedra
• On the diameter of partition polytopes and vertex-disjoint cycle cover
• Signature classes of transportation polytopes
• The Hirsch Conjecture for Dual Transportation Polyhedra
• The Hirsch conjecture is true for (0,1)-polytopes
• The Multi-Index Problem
• The circuit diameter of the Klee-Walkup polyhedron

Cited In (16)

• On the circuit diameter conjecture
• Circuits in extended formulations
• The diameters of network-flow polytopes satisfy the Hirsch conjecture
• Combinatorics and geometry of transportation polytopes: an update
• Factorized mutual information maximization.
• On circuit diameter bounds via circuit imbalances
• Proof of the Hirsch conjecture for a class of transportation polyhedra
• On the Combinatorial Diameters of Parallel and Series Connections
• Improved bounds on the diameter of lattice polytopes
• On the circuit diameter of some combinatorial polytopes
• Title not available (Why is no real title available?)
• An implementation of steepest-descent augmentation for linear programs
• On the circuit diameter of dual transportation polyhedra
• An O(\(n\)) bound for the diameter of transshipment polytopes
• Edges versus circuits: a hierarchy of diameters in polyhedra
• Circuit walks in integral polyhedra

This page was built for publication: The hierarchy of circuit diameters and transportation polytopes

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