The hierarchy of circuit diameters and transportation polytopes

DOI10.1016/J.DAM.2015.10.017zbMATH Open1383.05072DBLPjournals/dam/BorgwardtLFM18arXiv1411.1701OpenAlexW2210056327WikidataQ60242755 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)

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.

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

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

zbMATH Keywords

graph diametercircuit diameterHirsch conjecturetransportation polytopes

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (15)

• 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
• Improved bounds on the diameter of lattice polytopes
• On the circuit diameter of some combinatorial polytopes
• Title not available (Why is that?)
• 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)