Quadratic diameter bounds for dual network flow polyhedra

Steffen Borgwardt, Elisabeth Finhold, Raymond Hemmecke

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

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 languageEnglish
Pages (from-to)237-251
Number of pages15
JournalMathematical Programming
Volume159
Issue number1-2
DOIs
StatePublished - 1 Sep 2016

Keywords

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

Fingerprint

Dive into the research topics of 'Quadratic diameter bounds for dual network flow polyhedra'. Together they form a unique fingerprint.

Cite this