On the circuit diameter of dual transportation polyhedra

2014/05/13 by Borgwardt, Steffen, Finhold, Elisabeth, Hemmecke, Raymond · 1 citation
#52B05 #52B55 #90C05 #90C08 #90C10 #Combinatorics (math.CO) #FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1405.3184

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×N 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.

Cited by

• On Circuit Imbalance and 0/1 Circuits for Coloring and Spanning Forest Problems

Related

• The Hierarchy of Circuit Diameters and Transportation Polytopes
• Quadratic diameter bounds for dual network flow polyhedra
• Edges vs Circuits: a Hierarchy of Diameters in Polyhedra
• On the Circuit Diameter of some Combinatorial Polytopes
• On the Circuit Diameter Conjecture