Borgwardt, SteffenSteffenBorgwardtFinhold, ElisabethElisabethFinholdHemmecke, RaymondRaymondHemmeckeLoera, Jesús A. deJesús A. deLoera2022-03-052022-03-052016https://publica.fraunhofer.de/handle/publica/24649510.1007/s10107-015-0956-4Both the combinatorial and the circuit diameter of polyhedra are of interest to the theory of linear programming for their intimate connection to a best-case performance of linear programming algorithms. We study the diameters of dual network flow polyhedra associated to b-flows on directed graphs G=(V,E) and prove quadratic upper bounds for both of them: the minimum of (|V|−1)⋅|E| and 16|V|3 for the combinatorial diameter, and |V|⋅(|V|−1)2 for the circuit diameter. Previously, bounds on these diameters have only been known for bipartite graphs. The situation is much more involved for general graphs. In particular, we construct a family of dual network flow polyhedra with members that violate the circuit diameter bound for bipartite graphs by an arbitrary additive constant.en003006519journal article