On the Circuit Diameter of Dual Transportation Polyhedra

DOI10.1137/140976868zbMath1335.90058arXiv1405.3184OpenAlexW2962838697MaRDI QIDQ3453568

Elisabeth Finhold, Steffen Borgwardt, Raymond Hemmecke

Publication date: 27 November 2015

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

augmentationdiametercircuitlinear programinteger programgraver basisHirsch conjecturetest setelementary vector

Mathematics Subject Classification ID

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

Related Items (15)

Quadratic diameter bounds for dual network flow polyhedra ⋮ On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds--Karp to Bland and Beyond ⋮ The circuit diameter of the Klee-Walkup polyhedron ⋮ On circuit diameter bounds via circuit imbalances ⋮ An implementation of steepest-descent augmentation for linear programs ⋮ Circuit walks in integral polyhedra ⋮ Inapproximability of shortest paths on perfect matching polytopes ⋮ Edges versus circuits: a hierarchy of diameters in polyhedra ⋮ The hierarchy of circuit diameters and transportation polytopes ⋮ Constructing Clustering Transformations ⋮ On the Circuit Diameter of Some Combinatorial Polytopes ⋮ On the circuit diameter conjecture ⋮ A note on the approximability of deepest-descent circuit steps ⋮ A polyhedral model for enumeration and optimization over the set of circuits ⋮ Pivot Rules for Circuit-Augmentation Algorithms in Linear Optimization

This page was built for publication: On the Circuit Diameter of Dual Transportation Polyhedra