Quadratic diameter bounds for dual network flow polyhedra

Steffen Borgwardt, Elisabeth Finhold, Raymond Hemmecke

Both the combinatorial and the circuit diameters of polyhedra are of interest to the theory of linear programming for their intimate connection to a best-case performance of linear…