On the circuit diameter of dual transportation polyhedra

Steffen Borgwardt; Elisabeth Finhold; Raymond Hemmecke

doi:10.1137/140976868

On the circuit diameter of dual transportation polyhedra

Steffen Borgwardt, Elisabeth Finhold, Raymond Hemmecke

Computation, Information and Technology

Technical University of Munich

Research output: Contribution to journal › Article › peer-review

25 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 language	English
Pages (from-to)	113-121
Number of pages	9
Journal	SIAM Journal on Discrete Mathematics
Volume	29
Issue number	1
DOIs	https://doi.org/10.1137/140976868
State	Published - 2015

Keywords

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

Access to Document

10.1137/140976868

Cite this

@article{2be72c533c414bc79b3a66863736bb22,

title = "On the circuit diameter of dual transportation polyhedra",

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.",

keywords = "Augmentation, Circuit, Diameter, Elementary vector, Graver basis, Hirsch conjecture, Integer program, Linear program, Test set",

author = "Steffen Borgwardt and Elisabeth Finhold and Raymond Hemmecke",

note = "Publisher Copyright: {\textcopyright} 2015 Society for Industrial and Applied Mathematics.",

year = "2015",

doi = "10.1137/140976868",

language = "English",

volume = "29",

pages = "113--121",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "1",

}

TY - JOUR

T1 - On the circuit diameter of dual transportation polyhedra

AU - Borgwardt, Steffen

AU - Finhold, Elisabeth

AU - Hemmecke, Raymond

PY - 2015

Y1 - 2015

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

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

KW - Augmentation

KW - Circuit

KW - Diameter

KW - Elementary vector

KW - Graver basis

KW - Hirsch conjecture

KW - Integer program

KW - Linear program

KW - Test set

UR - http://www.scopus.com/inward/record.url?scp=84925365377&partnerID=8YFLogxK

U2 - 10.1137/140976868

DO - 10.1137/140976868

M3 - Article

AN - SCOPUS:84925365377

SN - 0895-4801

VL - 29

SP - 113

EP - 121

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 1

ER -

On the circuit diameter of dual transportation polyhedra

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this