On the circuit diameter of dual transportation polyhedra

Steffen Borgwardt, Elisabeth Finhold, Raymond Hemmecke

Research output: Contribution to journalArticlepeer-review

21 Scopus citations

Abstract

In this paper we introduce the circuit diameter of polyhedra, which is always bounded from above by the combinatorial diameter. We consider dual transportation polyhedra defined on general bipartite graphs. For complete M x N bipartite graphs the Hirsch bound (M-1)(N-1) on the combinatorial diameter is a known tight bound [Math. Oper. Res., 9 (1984), pp. 629-633]. For the circuit diameter we show the much stronger bound M+N-2 for all dual transportation polyhedra defined on arbitrary bipartite graphs with M+N nodes.

Original languageEnglish
Pages (from-to)113-121
Number of pages9
JournalSIAM Journal on Discrete Mathematics
Volume29
Issue number1
DOIs
StatePublished - 2015

Keywords

  • Augmentation
  • Circuit
  • Diameter
  • Elementary vector
  • Graver basis
  • Hirsch conjecture
  • Integer program
  • Linear program
  • Test set

Fingerprint

Dive into the research topics of 'On the circuit diameter of dual transportation polyhedra'. Together they form a unique fingerprint.

Cite this