On the Circuit Diameter of Dual Transportation Polyhedra
Steffen Borgwardt, Elisabeth Finhold, Raymond Hemmecke · SIAM Journal on Discrete Mathematics · 2015
Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.
SIAM Journal on Discrete Mathematics · Society for Industrial and Applied Mathematics · article · 2015
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{\times}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.
Open the resolved locator · 10.1137/140976868
Metadata licence: OpenAlex metadata (CC0)