On the circuit diameter of dual transportation polyhedra

DOI10.1137/140976868MaRDI QIDQ3453568zbMATH OpenOpenAlexFDO

Authors Steffen Borgwardt, Elisabeth Finhold, Raymond Hemmecke

Publication date 27 November 2015

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1405.3184

zbMATH Keywords

augmentationcircuitdiameterelementary vectorgraver basisHirsch conjectureinteger programlinear programtest set

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Linear programming (90C05) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Integer programming (90C10)

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 $MimesN$ bipartite graphs the Hirsch bound $(M-1)(N-1)$ on the combinatorial diameter is a known tight bound (Balinski, 1984). 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.

Recommendations

• The hierarchy of circuit diameters and transportation polytopes
• scientific article; zbMATH DE number 3845342
• An O(n) bound for the diameter of transshipment polytopes
• Quadratic diameter bounds for dual network flow polyhedra
• scientific article; zbMATH DE number 665698

Cited in

(31)

• An O(n) bound for the diameter of transshipment polytopes
• Edges versus circuits: a hierarchy of diameters in polyhedra
• The hierarchy of circuit diameters and transportation polytopes
• On the circuit diameter conjecture
• A note on the approximability of deepest-descent circuit steps
• A polyhedral model for enumeration and optimization over the set of circuits
• On circuit diameter bounds via circuit imbalances
• An implementation of steepest-descent augmentation for linear programs
• Circuit walks in integral polyhedra
• Quadratic diameter bounds for dual network flow polyhedra
• The Hirsch Conjecture for Dual Transportation Polyhedra
• The circuit diameter of the Klee-Walkup polyhedron
• scientific article; zbMATH DE number 3848970 (Why is no real title available?)
• On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds--Karp to Bland and Beyond
• scientific article; zbMATH DE number 3916323 (Why is no real title available?)
• On the diameter of partition polytopes and vertex-disjoint cycle cover
• On the circuit diameter of some combinatorial polytopes
• Constructing Clustering Transformations
• Pivot rules for circuit-augmentation algorithms in linear optimization
• Inapproximability of shortest paths on perfect matching polytopes
• Circuit Imbalance Measures and Linear Programming
• Circuits in extended formulations
• On circuit diameter bounds via circuit imbalances
• Circuit and Graver walks and linear and integer programming
• On combinatorial network flows algorithms and circuit augmentation for pseudoflows
• On the hardness of short and sign-compatible circuit walks
• Inapproximability of shortest paths on perfect matching polytopes
• Combinatorics of generalized parking-function polytopes
• On the circuit diameter conjecture for counterexamples to the Hirsch conjecture
• On circuit diameter and straight line complexity
• Sparse dual transportation polyhedra: Extreme points and signatures

This page was built for publication: On the circuit diameter of dual transportation polyhedra

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3453568)