## Abstract

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

Original language | English |
---|---|

Pages (from-to) | 237-251 |

Number of pages | 15 |

Journal | Mathematical Programming |

Volume | 159 |

Issue number | 1-2 |

DOIs | |

State | Published - 1 Sep 2016 |

## Keywords

- Circuit diameter
- Circuits
- Combinatorial diameter
- Edges
- Graver basis
- Hirsch conjecture
- Integer program
- Linear program