On the Circuit Diameter of Dual Transportation Polyhedra

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

zbMATH Keywords

augmentation; diameter; circuit; linear program; integer program; graver basis; Hirsch conjecture; test set; elementary vector

Mathematics Subject Classification ID

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.)