Quadratic diameter bounds for dual network flow polyhedra
From MaRDI portal
Publication:312672
DOI10.1007/s10107-015-0956-4zbMath1353.90083arXiv1408.4184OpenAlexW2149580763MaRDI QIDQ312672
Raymond Hemmecke, Elisabeth Finhold, Steffen Borgwardt
Publication date: 16 September 2016
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1408.4184
linear programminginteger programmingedgescircuitscircuit diametercombinatorial diametergraver basisHirsch conjecture
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
An implementation of steepest-descent augmentation for linear programs, Circuit walks in integral polyhedra, On the Circuit Diameter of Some Combinatorial Polytopes
Cites Work
- Unnamed Item
- Unnamed Item
- The circuit diameter of the Klee-Walkup polyhedron
- A counterexample to the Hirsch conjecture
- An update on the Hirsch conjecture
- The Hirsch conjecture is true for (0,1)-polytopes
- The \(d\)-step conjecture for polyhedra of dimension \(d<6\)
- The Hirsch Conjecture for Dual Transportation Polyhedra
- On the Circuit Diameter of Dual Transportation Polyhedra
- On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds--Karp to Bland and Beyond
- Combinatorics and Geometry of Transportation Polytopes: An Update
- On the foundations of linear and integer linear programming I