On the Circuit Diameter of Dual Transportation Polyhedra
From MaRDI portal
Publication:3453568
DOI10.1137/140976868zbMath1335.90058arXiv1405.3184MaRDI QIDQ3453568
Elisabeth Finhold, Raymond Hemmecke, Steffen Borgwardt
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
augmentation; diameter; circuit; linear program; integer program; graver basis; Hirsch conjecture; test set; elementary vector
52B05: Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)
90C10: Integer programming
90C05: Linear programming
90C08: Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
Related Items
On the Circuit Diameter of Some Combinatorial Polytopes, Quadratic diameter bounds for dual network flow polyhedra, The circuit diameter of the Klee-Walkup polyhedron, Edges versus circuits: a hierarchy of diameters in polyhedra, The hierarchy of circuit diameters and transportation polytopes, On the circuit diameter conjecture, On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds--Karp to Bland and Beyond