Quadratic diameter bounds for dual network flow polyhedra

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

zbMATH Keywords

linear programminginteger programmingedgescircuitscircuit diametercombinatorial diametergraver basisHirsch conjecture

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

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